Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 数组为什么要开1500000。。。。。。才能过，《贴代码》。。做了好久啊

Posted by 1083595345 at 2015-08-02 13:55:58 on Problem 2828
```#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn=1500000;//数组为何开这么大。。。

int tree[maxn],sum[maxn],num[maxn][2],n;

int sum_insert(int l,int r,int rt)
{
if(l==r) return sum[rt]=1;
return sum[rt]=sum_insert(l,(l+r)/2,rt*2)+sum_insert((l+r)/2+1,r,rt*2+1);
}

int insert(int pos,int val,int rt)
{
if(sum[rt*2]==-1) {tree[rt]=val;return sum[rt]-=1;}
if(sum[rt*2]<pos) return sum[rt]=sum[rt*2]+insert(pos-sum[rt*2],val,rt*2+1);
else return sum[rt]=sum[rt*2+1]+insert(pos,val,rt*2);
}

//int push_up(int l,int r,int rt) { if(l==r) return sum[rt]=tree[rt]?0:1; return sum[rt]=push_up(l,(l+r)/2,rt*2)+push_up((l+r)/2+1,r,rt*2+1); }

void output(int l,int r,int rt)
{
if(l==r) {printf("%d",tree[rt]);return ;}
output(l,(l+r)/2,rt*2);printf(" ");
output((l+r)/2+1,r,rt*2+1);
}

int main()
{
while(~scanf("%d",&n)){
memset(sum,-1,sizeof sum),memset(tree,0,sizeof tree);
sum_insert(1,n,1);
for(int i=0;i<n;i++) scanf("%d%d",&num[i][0],&num[i][1]);
for(int i=0;i<n;i++) num[i][0]+=1;
for(int i=n-1;i>=0;i--) insert(num[i][0],num[i][1],1);//push_up(1,n,1);贡献几次超时，其实可以同时完成
output(1,n,1); printf("\n");
}

return 0;
}
```

Followed by: