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 |
Re:我想自杀...写了N天,居然是如此之小的一个错误...离散化+树状数组,果然是名不虚传~In Reply To:我想自杀...写了N天,居然是如此之小的一个错误...离散化+树状数组,果然是名不虚传~ Posted by:DestinyDesigner at 2009-09-14 10:58:22 我也离散化+树状数组+二分查找,复杂度2*n*logn+m*logn*logn的。。tle了。。。 #include<iostream> #include<algorithm> using namespace std; int a[100006],sum[100006]; int index[100006]; int data[100006]; struct interval { int l,r,k; }in[50005]; inline bool operator<(const interval &a,const interval &b) { return a.l!=b.l?a.l<b.l:a.r<=b.r; } inline int lowbit(int t) { return t&(-t); } void update(int i,int s,int ind) { while(i<=ind) { sum[i]+=s; i+=lowbit(i); } return ; } int getsum(int i) { int ans=0; while(i>=1) { ans+=sum[i]; i-=lowbit(i); } return ans; } int find(int d,int ind) { int left=1,right=ind,mid; if(index[left]==d) return left; if(index[right]==d) return right; while(1) { mid=(left+right)>>1; if(index[mid]==d) break; if(index[mid]>d) right=mid; else left=mid; } return mid; } int process(int k,int ind) { int left=1,right=ind,mid; int p; p=getsum(left); if(a[left]&&p>=k&&p-a[left]<=k) return left; p=getsum(right); if(a[right]&&p>=k&&p-a[right]<=k) return right; while(1) { mid=(left+right)>>1; p=getsum(mid); if(a[mid]&&p>=k&&p-a[mid]<=k) break; if(p>=k) right=mid; else left=mid; } return mid; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",data+i); memcpy(index,data,sizeof(data)); memset(a,0,sizeof(a)); memset(sum,0,sizeof(sum)); sort(index+1,index+1+n); int ind=1; for(int i=1;i<n;i++) if(index[i]!=index[i+1]) index[ind++]=index[i]; index[ind]=index[n]; for(int i=1;i<=m;i++) scanf("%d%d%d",&in[i].l,&in[i].r,&in[i].k); sort(in+1,in+1+m); int ttt=0; for(int i=in[1].l;i<=in[1].r;i++) { int p=find(data[i],ind); update(p,1,ind); a[p]++; ttt=max(ttt,p); } for(int i=1;i<=m;i++) { if(i!=1) { int s=min(in[i].l,in[i-1].r); s+=(s==in[i-1].r?1:0); for(int j=in[i-1].l;j<s;j++) { int p=find(data[j],ind); update(p,-1,ind); a[p]--; } int t=max(in[i].l,in[i-1].r); for(int j=t+(t==in[i-1].r?1:0);j<=in[i].r;j++) { int p=find(data[j],ind); update(p,1,ind); a[p]++; ttt=max(ttt,p); } } printf("%d\n",index[process(in[i].k,ttt)]); } } } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator