Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贪心+树状数组#include<cstdio> using namespace std; const int N=50001; int a[N],b[N],c[N],t[N+1]; bool v[N+1]; void qsort(int l,int r) { int i=l,j=r,k=b[l+r>>1],tmp; while(i<=j) { while(b[i]<k)i++; while(b[j]>k)j--; if(i<=j) { tmp=a[i]; a[i]=a[j]; a[j]=tmp; tmp=b[i]; b[i]=b[j]; b[j]=tmp; tmp=c[i]; c[i]=c[j]; c[j]=tmp; i++; j--; } } if(i<r)qsort(i,r); if(l<j)qsort(l,j); } int sum(int x) { int res=0; while(x) { res+=t[x]; x-=x&-x; } return res; } void add(int x) { while(x<=N) { t[x]++; x+=x&-x; } } int main() { int n,i,j,tmp; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d%d%d",&a[i],&b[i],&c[i]); b[i]++; } qsort(1,n); for(i=1;i<=n;i++) { tmp=c[i]-(sum(b[i])-sum(a[i])); j=b[i]; while(tmp>0) { while(v[j])j--; v[j]=true; add(j); tmp--; } } printf("%d\n",sum(N)); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator