9272022-01-28 14:36:52Babják PéterHázakcpp11Elfogadva 100/100159ms31904 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms1780 KiB
2Elfogadva12ms4176 KiB
subtask215/15
3Elfogadva1ms2180 KiB
4Elfogadva2ms2420 KiB
5Elfogadva10ms3356 KiB
6Elfogadva12ms4676 KiB
7Elfogadva10ms4948 KiB
subtask315/15
8Elfogadva1ms2908 KiB
9Elfogadva1ms2948 KiB
10Elfogadva1ms2976 KiB
11Elfogadva2ms3128 KiB
12Elfogadva2ms3204 KiB
subtask420/20
13Elfogadva2ms3228 KiB
14Elfogadva4ms3416 KiB
15Elfogadva7ms4340 KiB
16Elfogadva12ms4836 KiB
17Elfogadva9ms5048 KiB
subtask550/50
18Elfogadva26ms7976 KiB
19Elfogadva35ms10092 KiB
20Elfogadva74ms15888 KiB
21Elfogadva133ms25700 KiB
22Elfogadva159ms31904 KiB