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

终于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){
				add(a[0].S,1);
				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);
				}
				add(a[i].S,1);
			}
		}

		for (int i = 0;i<N-1;++i){
			printf("%d ",ans[i]);}
		printf("%d\n",ans[N-1]);
	}	
	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