题解 P4602 【[CTSC2018]混合果汁】

Great_Influence

2018-05-16 19:37:37

Solution

来发一个不同的。 ## 整体二分 观察可以发现,答案明显具有单调性。但是一个个来二分的话,时间复杂度为$O(n^2log^2n)$的,明显无法通过此题。所以考虑整体二分,时间复杂度降为$O(nlog^2n)$,可以通过此题。 注意一下,每次都将左端点到最右边排序的话,时间复杂度会变成$O(n^2log^2n)$,直接挂成$60pts$。考虑用一个$multiset$维护果汁,时间复杂度可以保证。 代码: ```cpp #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i) #define For(i,a,b) for(i=(a),i<=(b);++i) #define Forward(i,a,b) for(i=(a),i>=(b);--i) template<typename T>inline void read(T &x) { T f=1;x=0;char c; for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=x*10+(c^48); x*=f; } using namespace std; void file() { #ifndef ONLINE_JUDGE freopen("water.in","r",stdin); freopen("water.out","w",stdout); #endif } const int MAXN=1e5+7; static int n,m; static struct juice { int d; long long p,l; }p[MAXN]; inline bool cmp1(juice a,juice b){return a.d<b.d;} static struct boy { long long g,l; int id; }q[MAXN],ret[MAXN]; inline bool cmp2(boy a,boy b){return a.g<b.g;} inline void init() { read(n);read(m); Rep(i,1,n)read(p[i].d),read(p[i].p),read(p[i].l); p[n+1].d=-1;p[n+1].p=0;p[n+1].l=1e18;++n; sort(p+1,p+n+1,cmp1); Rep(i,1,m)read(q[i].g),read(q[i].l),q[i].id=i; } static int ans[MAXN],pos; typedef pair<long long,int>Pr; static multiset<Pr>K; static multiset<Pr>::iterator it; void div(int l,int r,int x,int y) { if(x>y)return; if(l==r){Rep(i,x,y)ans[q[i].id]=p[l].d;return;} static int mid,lp,rp;mid=(l+r)>>1,lp=x,rp=y; static long long sm,cost;sm=0,cost=0; sort(q+x,q+y+1,cmp2); while(pos>mid+1)--pos,K.insert(Pr(p[pos].p,p[pos].l)); while(pos<mid+1)K.erase(K.lower_bound(Pr(p[pos].p,p[pos].l))) ,++pos; it=K.begin(); Rep(i,x,y) { while(it!=K.end()&&cost+it->first*it->second<=q[i].g) cost+=it->first*it->second,sm+=it->second,++it; //cerr<<sm<<' '<<cost<<' '<<q[i].l<<' '<<q[i].g<<endl; if(q[i].l<=sm||it!=K.end() &&sm+(q[i].g-cost)/it->first>=q[i].l) ret[rp--]=q[i]; else ret[lp++]=q[i]; } Rep(i,x,y)q[i]=ret[i]; div(mid+1,r,lp,y); div(l,mid,x,lp-1); } inline void solve() { pos=n+1;div(1,n,1,m); Rep(i,1,m)printf("%d\n",ans[i]); } int main() { file(); init(); solve(); //cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl; return 0; } ```