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

求助,为什么打问号的地方不能这么写,代码如下

Posted by nuhaiguhun at 2012-08-18 17:50:07 on Problem 2481
#include <stdio.h>
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxnum=100005;
struct node
{
    int l,r;
    int pos;
}array[maxnum];
int tree[maxnum];
int ans[maxnum];
int n;

bool cmp(struct node a,struct node b)
{
    if(a.r==b.r)
        return a.l<b.l;
    return a.r>b.r;
}

void update(int index,int add)
{
    while(index<=maxnum)
     {
        tree[index]+=add;
        index+=(-index)&index;
    }
}

int getsum(int index)
{
    int sum=0;
    while(index>0)
    {
        sum+=tree[index];
        index-=(-index)&index;
    }
    return sum;
}

int main()
{
    int i;
    while(scanf("%d",&n) && n!=0)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&array[i].l,&array[i].r);
            array[i].pos=i;
        }
        sort(array,array+n,cmp);
        memset(tree,0,sizeof(tree));
        int cnt=0;
        for(i=0;i<n;i++)
        {
            if(i!=0 && array[i].l==array[i-1].l && array[i].r==array[i-1].r)
            {
                ans[array[i].pos]=ans[array[i-1].pos]; 
                cnt++;
            }
            else
            {
                update(array[i].l+1,1);//????????????????
                ans[array[i].pos]=getsum(array[i].l+1)-1+cnt;//???????????
            }
        }
        for(i=0;i<n-1;i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[i]);
    }
    return 0;
}
打问号的地方的意思是,我只对不相同的坐标点进行update,如果相同的话,cnt++,然后在求和的时候把cnt加上。测试的几个用例都能通过,但是WA,真心求助大牛啊..

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