Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 终于AC了 贴代码庆祝一下

Posted by count_if at 2014-07-09 20:27:05 on Problem 2481
``` 两点：E可能等于0，所以要加一，以及注意前后奶牛相等的情况
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int  C[1000001];
int maxL;
int N;
struct point{
int S;
int E;
int index;
bool operator<(const point& rhs)const{
if (E == rhs.E)
return S<rhs.S;
return E>rhs.E;
}
}a[100005];
int lowbit(int x){
return x&(-x);
}
int sum(int x){
int ret = 0;
while(x>0){
ret += C[x];
x-=lowbit(x);
}
return ret;
}
void add(int x ,int d){
while(x<=maxL){
C[x] += d;
x += lowbit(x);
}
}

int main(){
while (true){
scanf("%d",&N);
if (N==0)
break;
int ans[1000000];
maxL = 0;
memset(C,0,sizeof(C));
memset(ans,0,sizeof(ans));
for (int i = 0;i<N;++i){
scanf("%d %d",&a[i].S,&a[i].E);
a[i].S ++;
a[i].E ++;
if (a[i].S > maxL)
maxL = a[i].S;
a[i].index = i;
}
sort(a,a+N);
for (int i = 0;i<N;++i){
if (i == 0){
continue;
}
if (i>0){
if (a[i].S == a[i-1].S && a[i].E== a[i-1].E)
ans[a[i].index]= ans[a[i-1].index];
else {
ans[a[i].index]= sum(a[i].S);
}
}
}

for (int i = 0;i<N-1;++i){
printf("%d ",ans[i]);}
printf("%d\n",ans[N-1]);
}
return 0;
}```

Followed by: