Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
WA已经不错了。好好查代码吧。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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator