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

Re:实在没办法了,贴一下自己WA的代码(有详细的注释),哪位大牛帮我看一下,或者给几组我过不了的数据,小弟不胜感激!!

Posted by acm_newer at 2009-09-21 19:20:45 on Problem 1828
In Reply To:实在没办法了,贴一下自己WA的代码(有详细的注释),哪位大牛帮我看一下,或者给几组我过不了的数据,小弟不胜感激!! Posted by:new_begin at 2009-09-20 02:09:49
> #include<iostream>
> #include<algorithm>
> 
> using namespace std;
> 
> const int N=50005;
> 
> struct point
> {
> 	int x,y;
> 	bool operator<(const point&bb)const
> 	{
> 		if(x!=bb.x)
> 			return x>bb.x;
> 		return y>bb.x;
> 	}
> } p[N];
> struct node
> {
> 	int y,num;
> 	bool operator<(const node&bb)const
> 	{
> 		return y<bb.y;
> 	}
> } q[N];
> int a[N],yy[N];
> int n;
> 
> int lowbit(int x)
> {
> 	return x&(-x);
> }
> int getsum(int x)
> {
> 	int i,sum;
> 	if(x==0)
> 		return 0;
> 	sum=0;
> 	i=x;
> 	while(i>0)
> 	{
> 		sum+=a[i];
> 		i-=lowbit(i);
> 	}
> 	return sum;
> }
> void change(int x)
> {
> 	int i=x;
> 	while(i<=n)
> 	{
> 		a[i]++;
> 		i+=lowbit(i);
> 	}
> 	return;
> }
> 
> int main()
> {
> 	int i,j,sum,u,v;
> 	while(scanf("%d",&n)==1&&n)
> 	{
> 		i=1;
> 		while(i<=n)
> 		{
> 			scanf("%d%d",&p[i].x,&p[i].y);
> 			i++;
> 		}
> 		sort(p+1,p+n+1);//对x坐标排序,如果x坐标相等,按y坐标排序。
> 
>                 //离散化,离散化后的y坐标值保存在yy数组中。
> 		i=1;
> 		while(i<=n)
> 		{
> 			q[i].y=p[i].y;
> 			q[i].num=i;
> 			i++;
> 		}
> 		sort(q+1,q+n+1);
> 		j=1;
> 		yy[q[1].num]=1;
> 		i=2;
> 		while(i<=n)
> 		{
> 			if(q[i].y!=q[i-1].y)
> 			{
> 				++j;
> 				yy[q[i].num]=j;
> 			}
> 			else yy[q[i].num]=j;
> 			i++;
> 		}
>                 //树状数组。
> 		memset(a,0,sizeof(a));
> 		change(yy[1]);//每插入一个y值,就在树状数组相应点加1。
> 		sum=1;
> 		i=2;
> 		while(i<=n)
> 		{
> 			change(yy[i]);
> 		    	u=getsum(yy[i]);
> 			    v=getsum(yy[i]-1);
>                         //当前y值比之前插入的y值都要大,则sum加1,即1到yy[i]得和为i,而yy[i]这点为1。
> 		    	if(u==i&&v==i-1)
> 				sum++;
> 			i++;
> 		}
> 		printf("%d\n",sum);
> 	}
> 	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