| ||||||||||
| 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