比赛 |
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;
}