| 记录编号 |
370693 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HEOI 2016] 序列 |
最终得分 |
100 |
| 用户昵称 |
 YGOI_真神名曰驴蛋蛋 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
5.003 s |
| 提交时间 |
2017-02-14 11:01:14 |
内存使用 |
11.74 MiB |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <algorithm>
typedef int node;
const int INF=~0U>>1;
const int MAXN=200100;
int D;
inline int input() {
static int c,k;k=0;
do c=getchar(); while(c<'0'||c>'9');
do k=k*10+c-'0',c=getchar(); while(c>='0'&&c<='9');
return k;
}
struct NODE {
int xx[2],yy[2],d[2];
int sum,v,size;
node ch[2];
NODE() {sum=v=size=0;xx[0]=xx[1]=yy[0]=yy[1]=d[0]=d[1]=0;ch[0]=ch[1]=0;}
NODE(const int&x,const int&y,const int&s) {
d[0]=xx[0]=xx[1]=x;
d[1]=yy[0]=yy[1]=y;
size=1;v=sum=s;
ch[0]=ch[1]=0;
}
bool operator < (const NODE&a) const {
return d[D]==a.d[D] ? d[!D]<a.d[!D]:d[D]<a.d[D];
}
bool operator == (const NODE&a)const {
return d[0]==a.d[0] and d[1]==a.d[1];
}
void operator += (const NODE&a){
v=std::max(v,a.v);
sum=std::max(sum,a.sum);
}
bool print(int c=0) const {
printf("seq:%2d (size:%2d){x:[%3d,%3d],y:[%3d,%3d]},sum:%4d|v:%4d,<l:%2d,r:%2d>\n",c,size,xx[0],xx[1],yy[0],yy[1],sum,v,ch[0],ch[1]);
return true;
}
};
NODE w[MAXN],temp;
inline bool cmp(const node&i,const node &j){
return w[i]<w[j];
}
struct K_D_T {
int cnt,pre;
node t[MAXN],rt;
inline bool in(int x1,int x2,int y1,int y2) const {
return temp.xx[0]<=x1
and x2<=temp.xx[1]
and temp.yy[0]<=y1
and y2<=temp.yy[1];
}
inline bool out(int x1,int x2,int y1,int y2) const {
return temp.xx[0]>x2
or x1>temp.xx[1]
or temp.yy[0]>y2
or y1>temp.yy[1];
}
void update(node c) {
if(!c)return ;
NODE &p=w[c];
NODE &l=w[p.ch[0]];
NODE &r=w[p.ch[1]];
p.size=1;
p.sum=p.v;
p.xx[0]=p.xx[1]=p.d[0];
p.yy[0]=p.yy[1]=p.d[1];
if(p.ch[0]) {
p.xx[0]=std::min(p.xx[0],l.xx[0]);
p.xx[1]=std::max(p.xx[1],l.xx[1]);
p.yy[0]=std::min(p.yy[0],l.yy[0]);
p.yy[1]=std::max(p.yy[1],l.yy[1]);
p.size+=l.size;
p.sum=std::max(p.sum,l.sum);
}
if(p.ch[1]) {
p.xx[0]=std::min(p.xx[0],r.xx[0]);
p.xx[1]=std::max(p.xx[1],r.xx[1]);
p.yy[0]=std::min(p.yy[0],r.yy[0]);
p.yy[1]=std::max(p.yy[1],r.yy[1]);
p.size+=r.size;
p.sum=std::max(p.sum,r.sum);
}
}
bool need7(node c) const {
static float is7=0.7;
return w[c].size*is7<w[w[c].ch[0]].size
||w[c].size*is7<w[w[c].ch[1]].size;
}
void travel(node c) {
if(!c)return;
travel(w[c].ch[0]);
t[++pre]=c;
travel(w[c].ch[1]);
}
#define mid ((l+r)>>1)
int build(int l,int r,int dept) {
if(l>r)return 0;
D=dept;
std::nth_element(t+l,t+mid,t+r+1,cmp);
int kid=t[mid];
w[kid].ch[0]=build(l,mid-1,dept^1);
w[kid].ch[1]=build(mid+1,r,dept^1);
update(kid);
//w[kid].print(kid);
return kid;
}
#undef mid
void rebuild(node &c,int dept) {
pre=0;travel(c);
c=build(1,pre,dept);
}
void insert(node&c,int dept) {
if(!c) {
c=++cnt;
w[c]=temp;
return ;
}if(w[c]==temp) {
w[c]+=temp;
return ;
}D=dept;
insert(w[c].ch[w[c]<temp],dept^1);
update(c);
}
void check(node&c,int dept) {
if(w[c]==temp) {
return ;
}D=dept;
if(need7(c)){rebuild(c,dept);return;}
else check(w[c].ch[w[c]<temp],dept^1);
}
int query(NODE&it) {
if(!it.sum)return 0;
//it.print();
if(in(it.xx[0],it.xx[1],it.yy[0],it.yy[1]))return it.sum;
if(out(it.xx[0],it.xx[1],it.yy[0],it.yy[1]))return 0;
int ans=0;
if(in(it.d[0],it.d[0],it.d[1],it.d[1]))ans=it.v;
return std::max(ans,std::max(query(w[it.ch[0]]),query(w[it.ch[1]])));
}
void Insert(int x,int y,int s) {
temp=NODE(x,y,s);
insert(rt,0);
check(rt,0);
}
int Query(int x1,int y1,int x2,int y2) {
if(rt==0)return 0;
//printf("TAT\n");
temp.xx[0]=x1;temp.xx[1]=x2;
temp.yy[0]=y1;temp.yy[1]=y2;
return query(w[rt]);
}
}sq;
int c[MAXN][3];
int main() {
freopen("heoi2016_seq.in","r",stdin);
freopen("heoi2016_seq.out","w",stdout);
int N,M;
N=input();M=input();
for(int i=1;i<=N;++i) {
c[i][0]=c[i][2]=c[i][1]=input();
}
for(int i=1;i<=M;++i) {
int a,b;
a=input();b=input();
if(c[a][1]<b)c[a][2]=std::max(c[a][2],b);
else c[a][0]=std::min(c[a][0],b);
}
int ans=0;
for(int i=1;i<=N;++i) {
int f=sq.Query(-INF,-INF,c[i][0],c[i][1])+1;
//printf("i:%d %d\n",i,f);
sq.Insert(c[i][1],c[i][2],f);
ans=std::max(ans,f);
}printf("%d\n",ans);
fclose(stdin);fclose(stdout);
return 0;
}