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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

求助!谁能帮忙看一下为什么RE啊?实在受不了了……

Posted by fuckqwerty at 2011-01-30 21:43:37 on Problem 1990
#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:
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