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

看到的数据都过了,这个程序怎么就过不了啊?(换成注释后面是可以过的)

Posted by andone at 2010-07-25 09:13:03 on Problem 2481
#include<iostream>
#include<algorithm>
#define MAX 100001
using namespace std;
int c[MAX],res[MAX];
struct node
{
     int s,e;
     int i;
     bool operator <(const node a)const
     {
         if(e==a.e)
            return s > a.s;
         return e < a.e;
     }
}cow[MAX];
int lowbit(int x)
{
    return x&(-x);
}
int getsum(int x)
{
    int sum=0;
    while(x > 0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void update(int x,int delta)
{
     while(x < MAX)
     {
         c[x]+=delta;
         x+=lowbit(x);
     }
}
int main()
{
    int n;
    while(EOF!=scanf("%d",&n) && n)
    {
        memset(c,0,sizeof(c));
        memset(res,0,sizeof(res));
        for(int i=1;i<=n;i++)
        {   scanf("%d%d",&cow[i].s,&cow[i].e);
            cow[i].s++; cow[i].e++; cow[i].i=i; 
        }
        sort(cow+1,cow+n+1);
        
        update(cow[n].s,1);
        for(int i=n-1;i>0;i--)
        {
           
           if( (cow[i].s==cow[i+1].s) && (cow[i].e==cow[i+1].e))   
            {
                res[cow[i].i]=getsum(cow[i+1].s-1); //res[cow[i].i]=res[cow[i+1].i]; 
            } 
           else
           {
                 res[cow[i].i]=getsum(cow[i].s);
           }
           update(cow[i].s,1);
        }
        for(int i=1;i<n;i++)
          cout<<res[i]<<" ";
        cout<<res[n]<<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