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

WA已经不错了。好好查代码吧。

Posted by yygy at 2014-07-27 16:13:22 on Problem 3067
In Reply To:求解,线段树这样写为何会WA? Posted by:phoenix_hjp at 2014-07-27 15:07:20
> #include<iostream>
> #include<cstdio>
> #include<cstdlib>
> #include<string.h>
> #include<math.h>
> #include<algorithm>
> #include<map>
> #include<vector>
> #include<queue>
> using namespace std;
> int n,m,k;
> struct node
> {
>     int a,b;
> }a[1005*1005];
> struct tree
> {
>     int l,r,sum;
> }tree[1005<<2];
> bool cmp(const node &a,const node &b)
> {
>     if(a.a==b.a)
> 		return a.b<b.b;
> 	return a.a<b.a;
> }
> void build(int l,int r,int now)
> {
> 	tree[now].l=l;
> 	tree[now].r=r;
> 	tree[now].sum=0;
> 	if(l==r)
> 		return ;
> 	int mid=(l+r)>>1;
> 	build(l,mid,now<<1);
> 	build(mid+1,r,now<<1|1);
> }
> void update(int t,int now)
> {
> 	if(tree[now].l==tree[now].r)
> 	{
> 		tree[now].sum++;
> 		return ;
> 	}
> 	int mid=(tree[now].l+tree[now].r)>>1;
> 	if(t<=mid)
> 	{
> 	   	update(t,now<<1);
> 	   	tree[now].sum=(tree[now<<1].sum);
> 	}
> 	else
> 	{
> 	   	update(t,now<<1|1);
>         tree[now].sum=(tree[now<<1].sum+tree[now<<1|1].sum);
> 	}
> }
> int main()
> {
> 	int t,cases=0;
> 	cin>>t;
> 	while(t--)
> 	{
> 		cin>>n>>m>>k;
> 		for(int i=0;i<k;i++)
> 		{
> 			int t1,t2;
> 			scanf("%d%d",&t1,&t2);
> 			a[i].a=t1;
> 			a[i].b=t2;
> 		}
> 		sort(a,a+k,cmp);
> 		build(1,m,1);
> 		long long ans=0;
> 		for(int i=0;i<k;i++)
> 		{
> 		    update(a[i].b,1);
> 			ans+=(i+1-tree[1].sum);
> 		}
> 		++cases;
> 		cout<<"Test case "<<cases<<": "<<ans<<endl;
> 	}
>     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