7
6
2015
0

bzoj 1651: [Usaco2006 Feb]Stall Reservations 专用牛棚

水题,树状数组差分一下就秒了,但显然跑的死慢= =,352ms是什么鬼。

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int c[1000010],n,a,b,mx;

int lowbit(int x){
	return x&(-x);
}

void modify(int x,int y){
	while(x<=1000005){
		c[x]+=y;
		x+=lowbit(x);
	}
}

int query(int x){
	int ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}

int main(){
	scanf("%d",&n);
	memset(c,0,sizeof(c));
	while(n--){
		scanf("%d%d",&a,&b);
		modify(a,1);
		modify(b+1,-1);
	}
	mx=-1;
	for(int i=1;i<=1000000;i++){
		mx=max(query(i),mx);
	}
	printf("%d\n",mx);
	return 0;
}
Category: 树状数组 | Tags: bzoj 树状数组 差分 | Read Count: 572

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com