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

请大佬帮我看一下,在自己电脑上和HDU上都跑得很快,在这里就超时,是有什么情况没考虑到吗?

Posted by 3269224138 at 2017-12-21 22:14:13 on Problem 2352
#include<cstdio>
#include<algorithm>
using namespace std;

int n,a,b,ans[150012],number;



struct node{
	int v,r,num,tot;
	node* ch[2];
	int cmp(int x) const{
	  if (x==v)
	    return -1;
	  return x<v? 0:1;
	}
	void maintain(){
	  num=tot;
	  if (ch[0]!=NULL)
	    num+=ch[0]->num;
	  if (ch[1]!=NULL)
	    num+=ch[1]->num;
	}
}* root;

void rotate(node* &o,int d){
	node* k=o->ch[d^1];
	o->ch[d^1]=k->ch[d];
	k->ch[d]=o;
	o->maintain();
	k->maintain();
	o=k;
}	

void insert(node* &o,int x){
	if (o==NULL)
	{
	  o=new node();
	  o->v=x,o->r=number,o->num=1,o->tot=1;
	  o->ch[0]=NULL,o->ch[1]=NULL;
	  return ;
	}
	int d=o->cmp(x);
	insert(o->ch[d],x);
	if (o->ch[d]->r > o->r)
	  rotate(o,d^1);
}

void insertfind(node* &o,int x){
	int d=o->cmp(x);
	if (d==-1)
	{
	  o->tot++;
	  o->r=number;
	  return ;
	}
	insertfind(o->ch[d],x);
	if (o->ch[d]->r > o->r)
	  rotate(o,d^1);
}

int find(node* o,int x){
	while (o!=NULL)
	{
	  int d=o->cmp(x);
	  if (d==-1)
	    return 1;
	  o=o->ch[d];
	}
	return 0;
}

long long read(){
	long long x=0,f=1;
	char ch=getchar();
	while (ch>'9'||ch<'0')
	{
	  if (ch=='-')
	    f=-1;
	  ch=getchar();
	}
	while (ch>='0'&&ch<='9')
	{
	  x=(x<<1)+(x<<3)+(ch^'0');
	  ch=getchar();
	}
	return x*f;
}


int main(){
	while (scanf("%d",&n)==1)
	{
	  a=read(),b=read();
	  root=NULL;
	  for (int i=0;i<=n;i++)
	    ans[i]=0;
	  root=new node();
	  root->v=a,root->r=1;
	  root->num=1,root->tot=1;
	  root->ch[0]=NULL,root->ch[1]=NULL;
	  ans[0]++;
	  for (register int i=2;i<=n;++i)
	  {
	    number=i;
	    a=read(),b=read();
	    if (find(root,a))
	      insertfind(root,a);
	    else
	      insert(root,a);
	    root->maintain();
	    if (root->ch[1]==NULL)
	      ans[root->num-1]++;
	    else
	      ans[root->num - root->ch[1]->num-1]++;
	  }
	  for (register int i=0;i<=n-1;++i)
	    printf("%d\n",ans[i]);
	}
	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