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

## 为啥我数组飘到2000005才过

Posted by 1663727338 at 2014-03-25 20:42:20 on Problem 2828
```#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

#define maxn 2000005
struct mn{int id;int pos;int val;}man[maxn];
struct T{int sum;}tree[maxn*3];
int leaves[maxn];
void build(int a,int b,int root)
{
tree[root].sum=b-a+1;
if(a==b)
{
//leaves[root]=a;
return;
}
int mid=(a+b)/2;
build(a,mid,root*2);
build(mid+1,b,root*2+1);
}

void insert(int pos,int id,int a,int b,int root)
{
if(a==b)
{
leaves[root]=id;

while(1)
{
if(root<1)break;
tree[root].sum--;
root>>=1;
}
return;
}
if(pos>tree[root].sum)return;
else
{
if(pos<=tree[root*2].sum)//left
{
insert(pos,id,a,(a+b)/2,root+root);
}
else //right
{
insert(pos-tree[root*2].sum,id,(a+b)/2+1,b,1+root+root);
}
}
}

void output(int a,int b,int root,int &s)
{
if(a==b)
{
if(s==1)
{
printf("%d",man[leaves[root]].val);
s=0;
}
else
{
printf(" %d",man[leaves[root]].val);
}
return;
}

output(a,(a+b)/2,root*2,s);
output((a+b)/2+1,b,root*2+1,s);
}
int main()
{

int N;
while(scanf("%d",&N)==1)
{
memset(tree,0,sizeof(tree));
memset(leaves,0,sizeof(leaves));
for(int i=1;i<=N;i++)
{
scanf("%d%d",&man[i].pos,&man[i].val);
man[i].id=i;
}

build(1,N,1);

for(int i=N;i>=1;i--)
{
insert(man[i].pos+1,man[i].id,1,N,1);
}
int d=1;
output(1,N,1,d);
printf("\n");
}

return 0;

}```

Followed by:

User ID:
Title:

Content: