927 2022. 01. 28 14:36:52 Babják Péter Házak cpp11 Elfogadva 100/100 159ms 31904 KiB
#include<bits/stdc++.h>
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL)
#define MAXN 300100
#define ll long long
#define int ll
using namespace std;
//Algoritmus: polár
struct pont
{
	int x,y,ind;	
};
int ford(pont a,pont b)
{
	if((ll)b.x*a.y<(ll)a.x*b.y)return 1;
	if((ll)b.x*a.y==(ll)a.x*b.y)return 0;
	if((ll)b.x*a.y>(ll)a.x*b.y)return -1;
}
int lvl[MAXN];
vector<pont>p;
vector<pont> ba;
vector<int>level;
struct cmp
{
	bool operator()(const pont &f,const pont &g)
	{
		if(f.x<g.x)return 1;
		if(f.x==g.x && f.y<g.y)return 1;
		return 0;
	}	
};
struct cmp2
{
	bool operator()(const pont &f,const pont &g)
	{
		int dir=ford(f,g);
		if(dir==0)return f.x<g.x;
		if(dir==1)return 0;
		return 1;
	}
};
struct cmp3
{
	bool operator()(const int &a,const int &b)
	{
		if(lvl[a]==lvl[b])return ba[a].x<ba[b].x;
		return lvl[a]>lvl[b];
	}
};
priority_queue<int,vector<int>,cmp3> pq;
bool pqban[MAXN];
bool visible[MAXN];
signed main()
{
	IO;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
    	int a,b,c,d;
    	cin>>a>>b>>c>>d;
    	ba.push_back({a,b,i});
    	swap(b,d);
    	p.push_back({a,b,i});
    	p.push_back({c,d,i});
	}
	sort(ba.begin(),ba.end(),cmp());//nlogn
	level.push_back(0);
	for(pont q:ba)//nlogn
	{
		vector<int>::iterator it;
		it=upper_bound(level.begin(),level.end(),q.y);
		if(it==level.end())
		{
			level.push_back(q.y);
			lvl[q.ind]=level.size()-1;
			continue;
		}
		int ind=it-level.begin();
		level[ind]=q.y;
		lvl[q.ind]=ind;
	}
	sort(p.begin(),p.end(),cmp2());//nlogn
	for(pont q:p)//nlogn
	{
		if(pqban[q.ind]==0)
		{
			pq.push(q.ind);
			pqban[q.ind]=1;
		}
		else pqban[q.ind]=0;
		while(pq.empty()==0 && pqban[pq.top()]==0) pq.pop();
		if(pq.empty()==0) visible[pq.top()]=1;
	}
	vector<int>ans;
	for(int i=0;i<n;i++)
	{
		if(visible[i]==1)ans.push_back(i);
	}
	cout<<ans.size()<<'\n';
	for(int u:ans)cout<<u+1<<" ";
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 2ms 1780 KiB
2 Elfogadva 12ms 4176 KiB
subtask2 15/15
3 Elfogadva 1ms 2180 KiB
4 Elfogadva 2ms 2420 KiB
5 Elfogadva 10ms 3356 KiB
6 Elfogadva 12ms 4676 KiB
7 Elfogadva 10ms 4948 KiB
subtask3 15/15
8 Elfogadva 1ms 2908 KiB
9 Elfogadva 1ms 2948 KiB
10 Elfogadva 1ms 2976 KiB
11 Elfogadva 2ms 3128 KiB
12 Elfogadva 2ms 3204 KiB
subtask4 20/20
13 Elfogadva 2ms 3228 KiB
14 Elfogadva 4ms 3416 KiB
15 Elfogadva 7ms 4340 KiB
16 Elfogadva 12ms 4836 KiB
17 Elfogadva 9ms 5048 KiB
subtask5 50/50
18 Elfogadva 26ms 7976 KiB
19 Elfogadva 35ms 10092 KiB
20 Elfogadva 74ms 15888 KiB
21 Elfogadva 133ms 25700 KiB
22 Elfogadva 159ms 31904 KiB