水题,树状数组差分一下就秒了,但显然跑的死慢= =,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; }