比赛 20120706 评测结果 WTTTTTTTTW
题目名称 校草 最终得分 0
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-07-06 11:41:38
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN=110000;
const int oo=MAXN*10;

int n,i,j,k;
bool ans[MAXN];

struct peo
{
	int a,b,c,d,num;
}A[MAXN];

struct node
{
	int key,fix;
	node *c[2];
	inline void clean()
	{
		c[0]=c[1]=NULL;
		key=fix=0;
	}
};
	
struct treap
{
	node *root,P[MAXN];
	int ps;
	treap()
	{
		ps=0;
		root=NULL;
	}
	void empty()
	{
		for (int i=1;i<=n;i++) P[i].clean();
		root=NULL;
		ps=0;
	}
	void rotate(node *&p,int d)
	{
		node *tmp=p;
		p=tmp->c[!d];
		tmp->c[!d]=p->c[d];
		p->c[d]=tmp;
	}
	void insert(node *&p,int key,int fix)
	{
		if (!p)
		{
			++ps;
			p=P+ps;
			p->key=key;
			p->fix=fix;
		} 
        else
		{
			if (key>p->key)
			{
				insert(p->c[1],key,fix);
				if (p->c[1]->fix<p->fix) rotate(p,0);
			}
			else
			{
				insert(p->c[0],key,fix);
				if (p->c[0]->fix<p->fix) rotate(p,1);
				}
			}
	}
	int find(node *p,int k)
	{
		if (!p) return oo;
		if (p->key<=k) return p->fix;
		return find(p->c[0],k);
	}
}T1,T2,T3;

inline int cmpa(const void *p,const void *q)
{
	return ((peo*)p)->a-((peo*)q)->a;
}

inline int cmpb(const void *p,const void *q)
{
	return ((peo*)p)->b-((peo*)q)->b;
}

int main()
{
	freopen("hjjhvf.in","r",stdin);
	freopen("hjjhvf.out","w",stdout);
	scanf("%d",&n);
	memset(ans,false,sizeof(ans));
	for (i=1;i<=n;i++)
	{
		scanf("%d%d%d%d",&A[i].a,&A[i].b,&A[i].c,&A[i].d);
		A[i].num=i;
	}
	if (n<=10000)
	{
		int tmp;
		for (i=1;i<n;i++)
			for (j=i+1;j<=n;j++)
			{
				tmp=A[i].a<A[j].a+A[i].b<A[j].b+A[i].c<A[j].c+A[i].d<A[j].c;
				if (tmp>=3) ans[j]=true;
				tmp=A[i].a>A[j].a+A[i].b>A[j].b+A[i].c>A[j].c+A[i].d>A[j].c;
				if (tmp>=3) ans[i]=true;
			}
	}
	else
	{
	qsort(A+1,n,sizeof(A[0]),cmpa);
	for (i=2;i<=n;i++)
	{
		if (i==5000)
		{
			i=5000;
		}
		T1.insert(T1.root,A[i-1].b,A[i-1].c);
		T2.insert(T2.root,A[i-1].b,A[i-1].d);
		T3.insert(T3.root,A[i-1].c,A[i-1].d);
		if (T1.find(T1.root,A[i].b-1)<A[i].c)
		{
			ans[A[i].num]=true;
			continue;
		}
		if (T2.find(T2.root,A[i].b-1)<A[i].d)
		{
			ans[A[i].num]=true;
			continue;
		}
		if (T3.find(T3.root,A[i].c-1)<A[i].d)
		{
			ans[A[i].num]=true;
			continue;
		}
	}
	T1.empty();
	qsort(A+1,n,sizeof(A[0]),cmpb);
	for (i=2;i<=n;i++)
		if (!ans[A[i].num])
		{
			T1.insert(T1.root,A[i-1].c,A[i-1].d);
			if (T1.find(T1.root,A[i].c-1)<A[i].d) ans[A[i].num]=true;
		}
	}
	k=0;
	for (i=1;i<=n;i++)
		if (ans[i]) ++k;
	printf("%d\n",k);
	for (i=1;i<=n;i++)
		if (ans[i]) printf("%d\n",i);
	return 0;
}