QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #653312 | #5069. Vacation | Shumomo | WA | 709ms | 225308kb | C++14 | 9.1kb | 2024-10-18 19:52:45 | 2024-10-18 19:52:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
long long num,c;
struct seg2{
long long a[200009],v[800009];
void build(int rt,int l,int r){
if(l==r){
v[rt]=a[l];
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
v[rt]=max(v[rt<<1],v[rt<<1|1]);
}
void update(int rt,int l,int r,int ll,long long xx){
if(l==r){
v[rt]=xx;
return;
}
int mid=(l+r)>>1;
if(ll<=mid)update(rt<<1,l,mid,ll,xx);
else update(rt<<1|1,mid+1,r,ll,xx);
v[rt]=max(v[rt<<1],v[rt<<1|1]);
return;
}
void change(int x,long long y){
if(a[x]==y)return;
a[x]=y;
update(1,1,num,x,y);
return;
}
long long query(int rt,int l,int r,int ll,int rr){
// cout<<rt<<" "<<l<<" "<<r<<" "<<ll<<" "<<rr<<" "<<v[rt]<<endl;
if(l>rr||r<ll)return 0;
if(l>=ll&&r<=rr)return v[rt];
int mid=(l+r)>>1;
return max(query(rt<<1,l,mid,ll,rr),query(rt<<1|1,mid+1,r,ll,rr));
}
}tr2,tr3;
struct seg1{
vector<long long> a,b,f,g,lazyf,lazyg,fl;
struct node{
long long fmx,gmx,ans;
node operator +(const node bb)const{
node rtn;
rtn.fmx=max(fmx,bb.fmx);
rtn.gmx=max(gmx,bb.gmx);
rtn.ans=max(ans,bb.ans);
rtn.ans=max(rtn.ans,fmx+bb.gmx);
return rtn;
}
};
vector<node> v;
void pushdown(int rt){
if(lazyf[rt]){
lazyf[rt<<1]+=lazyf[rt];
lazyf[rt<<1|1]+=lazyf[rt];
v[rt<<1].fmx+=lazyf[rt];
v[rt<<1|1].fmx+=lazyf[rt];
if(!fl[rt<<1])v[rt<<1].ans+=lazyf[rt];
if(!fl[rt<<1|1])v[rt<<1|1].ans+=lazyf[rt];
lazyf[rt]=0;
}
if(lazyg[rt]){
lazyg[rt<<1]+=lazyg[rt];
lazyg[rt<<1|1]+=lazyg[rt];
v[rt<<1].gmx+=lazyg[rt];
v[rt<<1|1].gmx+=lazyg[rt];
if(!fl[rt<<1])v[rt<<1].ans+=lazyg[rt];
if(!fl[rt<<1|1])v[rt<<1|1].ans+=lazyg[rt];
lazyg[rt]=0;
}
}
void build(int rt,int l,int r){
// cerr<<rt<<" "<<l<<" "<<r<<endl;
if(l==r){
v[rt].fmx=f[l];
v[rt].gmx=g[l];
v[rt].ans=-1000000009;
fl[rt]=1;
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
v[rt]=v[rt<<1]+v[rt<<1|1];
// cout<<rt<<" "<<l<<" "<<r<<" "<<v[rt].fmx<<" "<<v[rt].gmx<<" "<<v[rt].ans<<endl;
return;
}
node query1(int rt,int l,int r,int ll){
if(l==r)return v[rt];
int mid=(l+r)>>1;
pushdown(rt);
node tmp=v[rt<<1];
tmp.ans=tmp.gmx=0;
if(ll<=mid)return query1(rt<<1,l,mid,ll)+v[rt<<1|1];
else return tmp+query1(rt<<1|1,mid+1,r,ll);
}
node query2(int rt,int l,int r,int ll){
if(l==r)return v[rt];
int mid=(l+r)>>1;
pushdown(rt);
node tmp=v[rt<<1|1];
tmp.ans=tmp.fmx=0;
if(ll<=mid)return query2(rt<<1,l,mid,ll)+tmp;
else return v[rt<<1]+query2(rt<<1|1,mid+1,r,ll);
}
node query3(int rt,int l,int r,int ll){
if(l>ll){
node tmp=v[rt];
tmp.fmx=tmp.ans=0;
return tmp;
}
if(r<=ll){
node tmp=v[rt];
tmp.gmx=tmp.ans=0;
return tmp;
}
int mid=(l+r)>>1;
pushdown(rt);
return query3(rt<<1,l,mid,ll)+query3(rt<<1|1,mid+1,r,ll);
}
node query4(int rt,int l,int r,int ll,int rr){
if(l>=ll&&r<=rr)return v[rt];
if(l>rr){
node tmp;
tmp.gmx=tmp.fmx=tmp.ans=0;
return tmp;
}
if(r<ll){
node tmp=v[rt];
tmp.gmx=tmp.ans=0;
return tmp;
}
int mid=(l+r)>>1;
pushdown(rt);
return query4(rt<<1,l,mid,ll,rr)+query4(rt<<1|1,mid+1,r,ll,rr);
}
long long Query1(int x){
node rtn=query1(1,1,c,x);
long long tmp=max(rtn.ans,rtn.fmx);
return max(tmp,rtn.gmx);
}
long long Query2(int x){
node rtn=query2(1,1,c,x);
long long tmp=max(rtn.ans,rtn.fmx);
return max(tmp,rtn.gmx);
}
long long Query3(int l,int r){
node rtn=query3(1,1,c,r);
long long tmp=max(0ll,rtn.fmx)+max(0ll,rtn.gmx);
rtn=query4(1,1,c,l,r);
tmp=max(tmp,rtn.gmx);
tmp=max(tmp,rtn.fmx);
tmp=max(tmp,rtn.ans);
return tmp;
}
void update1(int rt,int l,int r,int ll,int rr,long long xx){
if(l>rr||r<ll)return;
if(l>=ll&&r<=rr){
// cout<<rt<<" "<<l<<" "<<r<<" "<<lazyf[rt]<<" "<<v[rt].gmx<<" "<<v[rt].fmx<<" "<<v[rt].ans<<endl;
lazyg[rt]+=xx;
v[rt].gmx+=xx;
if(l!=r)v[rt].ans+=xx;
// cout<<rt<<" "<<l<<" "<<r<<" "<<lazyf[rt]<<" "<<v[rt].gmx<<" "<<v[rt].fmx<<" "<<v[rt].ans<<endl;
return;
}
int mid=(l+r)>>1;
pushdown(rt);
update1(rt<<1,l,mid,ll,rr,xx);
update1(rt<<1|1,mid+1,r,ll,rr,xx);
v[rt]=v[rt<<1]+v[rt<<1|1];
}
void update2(int rt,int l,int r,int ll,int rr,long long xx){
if(l>rr||r<ll)return;
if(l>=ll&&r<=rr){
// cout<<rt<<" "<<l<<" "<<r<<" "<<lazyf[rt]<<" "<<v[rt].gmx<<" "<<v[rt].fmx<<" "<<v[rt].ans<<endl;
lazyf[rt]+=xx;
v[rt].fmx+=xx;
if(l!=r)v[rt].ans+=xx;
// cout<<rt<<" "<<l<<" "<<r<<" "<<lazyf[rt]<<" "<<v[rt].gmx<<" "<<v[rt].fmx<<" "<<v[rt].ans<<endl;
return;
}
int mid=(l+r)>>1;
pushdown(rt);
update2(rt<<1,l,mid,ll,rr,xx);
update2(rt<<1|1,mid+1,r,ll,rr,xx);
v[rt]=v[rt<<1]+v[rt<<1|1];
// cout<<rt<<" "<<l<<" "<<r<<" "<<lazyf[rt]<<" "<<v[rt].gmx<<" "<<v[rt].fmx<<" "<<v[rt].ans<<endl;
}
void bbuild(){
for(int i=1;i<=c;i++)f[i]=f[i-1]+b[i];
for(int i=c;i;i--)g[i]=g[i+1]+a[i];
// cerr<<a.size()<<" "<<b.size()<<" "<<v.size()<<endl;
build(1,1,c);
return;
}
void change1(int x,long long y){
if(a[x]==y)return;
update1(1,1,c,1,x,y-a[x]);
a[x]=y;
}
void change2(int x,long long y){
if(b[x]==y)return;
update2(1,1,c,x,c,y-b[x]);
b[x]=y;
}
}tr1;
struct seg0{
struct node{
long long ls,rs,ss,mx;
node operator +(const node bb){
node rtn;
rtn.ls=max(ls,ss+bb.ls);
rtn.rs=max(rs+bb.ss,bb.rs);
rtn.ss=ss+bb.ss;
rtn.mx=max(mx,bb.mx);
rtn.mx=max(rtn.mx,rs+bb.ls);
return rtn;
}
}v[1000009];
long long a[200009];
void build(int rt,int l,int r){
if(l==r){
v[rt].ls=v[rt].rs=v[rt].ss=v[rt].mx=a[l];
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
v[rt]=v[rt<<1]+v[rt<<1|1];
}
void update(int rt,int l,int r,int ll,int yy){
if(l==r){
a[ll]=yy;
v[rt].ls=v[rt].rs=v[rt].ss=v[rt].mx=yy;
return;
}
int mid=(l+r)>>1;
if(ll<=mid)update(rt<<1,l,mid,ll,yy);
else update(rt<<1|1,mid+1,r,ll,yy);
v[rt]=v[rt<<1]+v[rt<<1|1];
}
node query(int rt,int l,int r,int ll,int rr){
if(l>=ll&&r<=rr)return v[rt];
int mid=(l+r)>>1;
if(ll<=mid&&rr>mid)return query(rt<<1,l,mid,ll,rr)+query(rt<<1|1,mid+1,r,ll,rr);
if(ll<=mid)return query(rt<<1,l,mid,ll,rr);
else return query(rt<<1|1,mid+1,r,ll,rr);
}
} tr0;
int main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
long long n,m,bl[200009],lb[200009],a[200009],op,x,y,ans;
scanf("%lld%lld%lld",&n,&m,&c);
num=c;
bl[0]=0;
for(int i=1;i<=n;i++){
scanf("%lld",a+i);
num++;
if(num<=c){
bl[i]=bl[i-1];
lb[i]=num;
}
else{
bl[i]=bl[i-1]+1;
lb[i]=1;
num=1;
}
}
num=bl[n];
vector<seg1> tr1;
tr1.resize(num+2);
for(int i=1;i<=num;i++){
tr1[i].a.resize(c+2);
tr1[i].b.resize(c+2);
tr1[i].g.resize(c+2);
tr1[i].f.resize(c+2);
tr1[i].fl.resize((c+2)<<2);
tr1[i].lazyf.resize((c+2)<<2);
tr1[i].lazyg.resize((c+2)<<2);
tr1[i].v.resize((c+2)<<2);
}
for(int i=1;i<=n;i++){
tr1[bl[i]].a[lb[i]]=a[i];
if(bl[i]>1)tr1[bl[i]-1].b[lb[i]]=a[i];
tr0.a[i]=a[i];
}
tr0.build(1,1,n);
for(int i=1;i<=num;i++){
// cerr<<i<<endl;
tr1[i].bbuild();
// cout<<i<<endl;
tr2.a[i]=tr0.query(1,1,n,i*c-c+1,i*c).mx;
// cout<<i<<" "<<tr2.a[i]<<endl;
tr3.a[i]=tr1[i].v[1].ans;
// cout<<tr1[i].v[1].ans<<endl;
}
tr2.build(1,1,num);
tr3.build(1,1,num);
for(int i=1;i<=m;i++){
// cout<<i<<endl;
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld",&x,&y);
// cout<<bl[x]<<endl;
tr0.update(1,1,n,x,y);
tr1[bl[x]].change1(lb[x],y);
if(bl[x]>1)tr1[bl[x]-1].change2(lb[x],y);
tr2.change(bl[x],tr0.query(1,1,n,bl[x]*c-c+1,bl[x]*c).mx);
// cout<<tr1[bl[x]].v[1].ans<<endl;
// cout<<tr1[bl[x]-1].v[1].ans<<" aaa"<<endl;
tr3.change(bl[x],tr1[bl[x]].v[1].ans);
if(bl[x]>1)tr3.change(bl[x]-1,tr1[bl[x]-1].v[1].ans);
}
else{
scanf("%lld%lld",&x,&y);
// cout<<x<<" "<<y<<" ";
if(y-x+1<=c){
printf("%lld\n",max(tr0.query(1,1,n,x,y).mx,0ll));
}
else if(bl[y]==bl[x]+1){
ans=tr1[bl[x]].Query3(lb[x],lb[y]);
// cout<<ans<<endl;
ans=max(ans,tr0.query(1,1,n,x,x+c-1).mx);
ans=max(ans,tr0.query(1,1,n,y-c+1,y).mx);
// cout<<tr0.query(1,1,n,x,x+c-1).mx<<" "<<tr0.query(1,1,n,y-c+1,y).mx<<endl;
printf("%lld\n",max(ans,0ll));
}
else if(bl[y]==bl[x]+2){
ans=max(tr1[bl[x]].Query1(lb[x]),tr1[bl[y]-1].Query2(lb[y]));
ans=max(ans,tr2.a[bl[x]+1]);
ans=max(ans,tr0.query(1,1,n,x,x+c-1).mx);
ans=max(ans,tr0.query(1,1,n,y-c+1,y).mx);
printf("%lld\n",max(ans,0ll));
}
else{
// cout<<ans<<endl;
ans=max(tr1[bl[x]].Query1(lb[x]),tr1[bl[y]-1].Query2(lb[y]));
// cout<<tr1[bl[x]].Query1(lb[x])<<" "<<tr1[bl[y]-1].Query2(lb[y])<<endl;
// cout<<ans<<endl;
ans=max(ans,tr2.query(1,1,num,bl[x]+1,bl[y]-1));
// cout<<ans<<endl;
ans=max(ans,tr3.query(1,1,num,bl[x]+1,bl[y]-2));
// cout<<ans<<endl;
ans=max(ans,tr0.query(1,1,n,x,x+c-1).mx);
// cout<<ans<<endl;
ans=max(ans,tr0.query(1,1,n,y-c+1,y).mx);
// cout<<ans<<endl;
printf("%lld\n",max(ans,0ll));
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 17032kb
input:
5 6 3 0 -5 -3 8 -3 2 3 5 1 2 5 2 1 5 1 4 -3 2 3 5 2 1 5
output:
8 10 0 5
result:
ok 4 number(s): "8 10 0 5"
Test #2:
score: 0
Accepted
time: 709ms
memory: 225308kb
input:
200000 500000 1 387060158 961744470 37167782 737122872 -532977662 1604246 -30977399 871848791 444997246 454204578 -813187501 -660394286 448014171 -835115276 -631880452 887715308 258530352 805589560 -414653327 -156732249 -335096199 -80266237 367896009 738406627 -903652056 446120866 415658444 -1347916...
output:
999902477 999981999 999343404 999847372 999957587 998160312 999981999 999981999 999981999 999980061 999981999 999981999 999981999 999876122 999981999 999996602 999981999 999981999 999981999 999723649 999981999 999957587 999896087 999981999 999981999 999981999 999981999 999981999 999957587 999981999 ...
result:
ok 250051 numbers
Test #3:
score: -100
Wrong Answer
time: 689ms
memory: 106664kb
input:
200000 500000 5 802774074 383481934 -295470374 285359286 751657057 197444479 626916547 -828168464 288373833 -493446966 -208422769 956745384 919286225 959643271 -176531848 -380256966 357111771 -50890039 -637284768 -337010918 259019684 752475630 -259898780 98620995 -704832505 -532710796 -971600790 -84...
output:
4544135313 4544135313 4443416295 3390067591 4544135313 4544135313 4322308420 4386413596 4386413596 4165697630 4322308420 4287938127 4443416295 4544135313 4386413596 4165697630 4386413596 4386413596 4386413596 4323325838 4443416295 4386413596 4385851999 4544135313 4443416295 4443416295 4323325838 432...
result:
wrong answer 56434th numbers differ - expected: '3008859415', found: '3058546175'