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 |
求助!谁能帮忙看一下为什么RE啊?实在受不了了……#include<stdio.h> #include<time.h> struct SEG { int l; int r; int mid; long long n; long long sum; }a[300000]; long long cow[200010][2]; int n; long long rn; long long rsum; long long ans; long long rdv; int rand() { rdv*=16807; rdv%=2147483647; return (int)rdv; } void build(int l,int r,int pos) { a[pos].l=l; a[pos].r=r; a[pos].mid=(l+r)>>1; a[pos].n=a[pos].sum=0; if(l==r)return; build(l,a[pos].mid,pos<<1); build(a[pos].mid+1,r,pos<<1|1); } void color(int x,int pos) { a[pos].n++; a[pos].sum+=x; if(a[pos].l==a[pos].r)return; int mid=a[pos].mid; if(x<=mid) color(x,pos<<1); else color(x,pos<<1|1); } void ask(int l,int r,int pos) { if(a[pos].l==l&&a[pos].r==r) { rn+=a[pos].n; rsum+=a[pos].sum; return; } int mid=a[pos].mid; if(r<=mid) ask(l,r,pos<<1); else if(mid+1<=l) ask(l,r,pos<<1|1); else { ask(l,mid,pos<<1); ask(mid+1,r,pos<<1|1); } } void exchange(int x,int y) { long long tmp; tmp=cow[x][0];cow[x][0]=cow[y][0];cow[y][0]=tmp; tmp=cow[x][1];cow[x][1]=cow[y][1];cow[y][1]=tmp; } int part(int p,int r) { int sb=rand(); sb=sb-(sb/(r-p))*(r-p); exchange(r,sb+p); long long x=cow[r][0]; int i=p-1; int j; for(j=p;j<r;j++) if(cow[j][0]<=x) exchange(++i,j); exchange(++i,r); return i; } void qs(int p,int r) { if(p>=r)return; int q=part(p,r); qs(p,q-1); qs(q+1,r); } int main() { int i,j; int sb1,sb2; int maxn=0; rdv=(long long)time(NULL); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%I64d%I64d",&cow[i][0],&cow[i][1]); if(cow[i][1]>maxn)maxn=cow[i][1]; } build(1,maxn,1); qs(1,n); for(i=1;i<=n;i++) { rsum=rn=0; ask(1,cow[i][1],1); ans+=cow[i][0]*(rn*cow[i][1]-rsum); rsum=rn=0; ask(cow[i][1],maxn,1); ans+=cow[i][0]*(rsum-rn*cow[i][1]); color(cow[i][1],1); } printf("%I64d\n",ans); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator