Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

为啥我数组飘到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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator