uoj386 鸽子固定器

uoj386 鸽子固定器

​​ 考虑枚举每个右端点 然后可以用一个堆维护区间最小值 然后当我们发现我们如果把枚举的右端点都弹出的时候一定break因为剩下的我们可以简单通过左移右端点使得答案变成更优的

另外我们可以用一个链表维护如果这个节点在这次i加入的时候并没有被加入那么说明之后我再被加入的时候一定不会被加入 因为我右端点在右移 所以说我至少应该已经有了m个满足条件的点我继续使用那满足条件的m个点即可 pow 竟然炸精度 我wtf!!!

#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=2e5+10;struct node{ int s,v;}data[N];int n,m,ds,dv,pre[N];inline bool cmp(const node &a,const node &b){return a.s,greater >q; for (int j=1;j<=m;++j) q.push(0);int now=i,last=0;ll sum=0; while(now){ int y=q-(); if (data[now].v>y){ sum+=data[now].v-y;q.pop();q.push(data[now].v); if (q-()>data[i].v) break; ans=max(ans,update(sum,data[i].s-data[now].s)); pre[last]=now;last=now; }now=pre[now]; }pre[last]=now; }printf("%lld\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。