#include #define ll long long #define mid (l+r>>1) #define rep(x,y,z) for(int x=(y);x<=(z);x++) #define per(x,y,z) for(int x=(y);x>=(z);x--) #define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i]) #define Pi pair #define pb push_back #define ui unsigned ll inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57){if(c=='-')w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-'0',c=getchar();return s*w;} const int N=2e5+5,M=1e6+5,inf=(1LL<<31)-1; const ll llf=1e18; using namespace std; int n,m,k,d,lsh[N],b[N],ln,testid,T;//days,tasks,limits,costs struct node{ int l,r,k; }a[N]; inline void init(){ ln=0; n=read(),m=read(),k=read(),d=read(); lsh[m*2+1]=0; rep(i,1,m){ a[i].r=read(),a[i].l=a[i].r-read()+1,a[i].k=read(); lsh[(i<<1)-1]=a[i].l,lsh[i<<1]=a[i].r; } sort(lsh+1,lsh+m*2+1); rep(i,2,m*2+1)if(lsh[i]^lsh[i-1])b[++ln]=lsh[i-1];//离散化 } ll dp[N]; inline ll got(int x){ if(x>=0)return dp[x]; return 0; } vectorp[N]; #define E(x) for(auto y:p[x]) #define L x<<1 #define R L|1 #define lc L,l,mid #define rc R,mid+1,r #define OK Ll<=l&&r<=Rr struct seg{ ll w,laz; }xd[N<<2]; inline void insert(int x,ll k){ xd[x].w+=k,xd[x].laz+=k; } inline void pushdown(int x){ insert(L,xd[x].laz),insert(R,xd[x].laz),xd[x].laz=0; } inline void getup(int x){ xd[x].w=max(xd[L].w,xd[R].w); } inline void build(int x,int l,int r){ xd[x]={0,0}; if(l==r)return; build(lc),build(rc); } inline void modify(int x,int l,int r,int Ll,int Rr,ll k){ if(OK)return insert(x,k),void(); pushdown(x); if(Ll<=mid&&Rr>=l)modify(lc,Ll,Rr,k); if(Ll<=r&&Rr>mid)modify(rc,Ll,Rr,k); getup(x); } inline ll query(int x,int l,int r,int Ll,int Rr){ if(Ll>Rr)return 0; if(OK)return xd[x].w; pushdown(x); if(Rr<=mid)return query(lc,Ll,Rr); if(Ll>mid)return query(rc,Ll,Rr); return max(query(lc,Ll,Rr),query(rc,Ll,Rr)); } //线段树 #define Root 1,1,ln inline int find(int x){ int l=1,r=ln,ans=r; while(l<=r)if(b[mid]>=x)ans=mid,r=mid-1; else l=mid+1; return ans; }//手写二分 inline void subtaskall(){ build(Root); rep(i,0,ln)dp[i]=0; rep(i,1,m){ a[i].l=lower_bound(b+1,b+ln+1,a[i].l)-b; a[i].r=lower_bound(b+1,b+ln+1,a[i].r)-b; p[a[i].r].pb({a[i].l,a[i].k}); } rep(i,1,ln){ E(i)modify(Root,1,y.first,y.second); int j=find(b[i]-k+1); dp[i]=max(dp[i],query(Root,j,i-1))-1LL*b[i]*d-1LL*d; int pos=i-2; if(b[i-1]!=b[i]-1)pos=i-1; dp[i]=max(dp[i],query(Root,i,i)+got(pos)-d); dp[i]=max(dp[i],dp[i-1]); modify(Root,i,i,got(pos)+1LL*b[i]*d); } cout <

题库

题库

3470.[NOIP2023] 天天爱打卡

题解大全 共 0 篇

测试用例

题解大全共 0 篇