QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#650109 | #5069. Vacation | sunkaihuan | WA | 874ms | 58280kb | C++14 | 5.4kb | 2024-10-18 13:01:51 | 2024-10-18 13:01:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
typedef long long ll;
int n,q,c,a[N],pr[N],nx[N],id[N];
struct sgt1{
struct st{
ll lmx,rmx,mx,sum;
}t[N<<2];
void pushup(st &p,st p1,st p2){
p.sum=p1.sum+p2.sum;
p.mx=max({p1.mx,p2.mx,p1.rmx+p2.lmx});
p.lmx=max(p1.lmx,p2.lmx+p1.sum);
p.rmx=max(p2.rmx,p1.rmx+p2.sum);
}
void build(int p,int l,int r){//cout<<p<<" "<<l<<" "<<r<<"\n";
if(l==r){t[p].mx=t[p].lmx=t[p].rmx=t[p].sum=a[l];return;}
int mid=(l+r)>>1;build(p*2,l,mid),build(p*2+1,mid+1,r);pushup(t[p],t[p*2],t[p*2+1]);
}
void ch(int p,int l,int r,int pt,int v){
if(l==r){t[p].mx=t[p].lmx=t[p].rmx=t[p].sum=v;return;}int mid=(l+r)>>1;
if(pt<=mid)ch(p*2,l,mid,pt,v);else ch(p*2+1,mid+1,r,pt,v);pushup(t[p],t[p*2],t[p*2+1]);
}
st ask(int p,int l,int r,int ll,int rr){
if(ll<=l&&r<=rr)return t[p];int mid=(l+r)>>1;st res;
if(rr<=mid)return ask(p*2,l,mid,ll,rr);
if(ll>mid)return ask(p*2+1,mid+1,r,ll,rr);
pushup(res,ask(p*2,l,mid,ll,rr),ask(p*2+1,mid+1,r,ll,rr));
return res;
}
}t1;
struct sgt2{
struct st{
ll sum[2],tg[2],mx;
}t[N<<2];
void pushup(st &p,st p1,st p2){
p.sum[0]=max(p1.sum[0],p2.sum[0]);
p.sum[1]=max(p1.sum[1],p2.sum[1]);
p.mx=max({p1.mx,p2.mx,p1.sum[0]+p2.sum[1]});
}
void pushdown(int p){
if(t[p].tg[0]!=0){
t[p*2].sum[0]+=t[p].tg[0];t[p*2+1].sum[0]+=t[p].tg[0];
t[p*2].tg[0]+=t[p].tg[0];t[p*2+1].tg[0]+=t[p].tg[0];
t[p*2].mx+=t[p].tg[0],t[p*2+1].mx+=t[p].tg[0];t[p].tg[0]=0;
}
if(t[p].tg[1]!=0){
t[p*2].sum[1]+=t[p].tg[1];t[p*2+1].sum[1]+=t[p].tg[1];
t[p*2].tg[1]+=t[p].tg[1];t[p*2+1].tg[1]+=t[p].tg[1];
t[p*2].mx+=t[p].tg[1],t[p*2+1].mx+=t[p].tg[1];t[p].tg[1]=0;
}
}
void build(int p,int l,int r){
if(l==r){
t[p].sum[0]=pr[l],t[p].sum[1]=nx[l];
t[p].tg[0]=t[p].tg[1]=0;t[p].mx=-4000000000000000000ll;return;
}int mid=(l+r)>>1;build(p*2,l,mid),build(p*2+1,mid+1,r);
pushup(t[p],t[p*2],t[p*2+1]);//cerr<<p<<" "<<l<<" "<<r<<" "<<t[p].mx<<" "<<t[p].sum[0]<<" "<<t[p].sum[1]<<"\n";
}
void add(int p,int l,int r,int ll,int rr,long long v,int w){
if(ll<=l&&r<=rr){t[p].mx+=v,t[p].sum[w]+=v,t[p].tg[w]+=v;return;}int mid=(l+r)>>1;pushdown(p);
if(ll<=mid)add(p*2,l,mid,ll,rr,v,w);if(rr>mid)add(p*2+1,mid+1,r,ll,rr,v,w);pushup(t[p],t[p*2],t[p*2+1]);
}
st ask(int p,int l,int r,int ll,int rr){//cerr<<p<<" "<<l<<" "<<r<<" "<<ll<<" "<<rr<<"\n";
if(ll<=l&&r<=rr){return t[p];}
int mid=(l+r)>>1;pushdown(p);st res;
if(rr<=mid)return ask(p*2,l,mid,ll,rr);
if(ll>mid)return ask(p*2+1,mid+1,r,ll,rr);
pushup(res,ask(p*2,l,mid,ll,rr),ask(p*2+1,mid+1,r,ll,rr));
return res;
}
}t2;
struct sgt3{
ll mx[N<<2];
void pushup(int p){mx[p]=max(mx[p*2],mx[p*2+1]);}
void ch(int p,int l,int r,int pt,ll v){
if(l==r){mx[p]=v;return;}int mid=(l+r)>>1;
if(pt<=mid)ch(p*2,l,mid,pt,v);
else ch(p*2+1,mid+1,r,pt,v);pushup(p);
}
ll ask(int p,int l,int r,int ll,int rr){
if(ll<=l&&r<=rr)return mx[p];int mid=(l+r)>>1;
if(rr<=mid)return ask(p*2,l,mid,ll,rr);
if(ll>mid)return ask(p*2+1,mid+1,r,ll,rr);
return max(ask(p*2,l,mid,ll,rr),ask(p*2+1,mid+1,r,ll,rr));
}
}t3,t4;
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0); cin>>n>>q>>c;
for(int i=1;i<=n;i++)cin>>a[i];n++;
while(n%c)n++;t1.build(1,1,n);//cout<<n<<"\n";
for(int i=1;i<=n;i++)id[i]=(i-1)/c+1;
for(int i=c+1;i<=n;i++){
if(id[i]!=id[i-1])pr[i-c]=0;
else pr[i-c]=pr[i-c-1];pr[i-c]+=a[i];//,cerr<<pr[i-c]<<"\n";
}
for(int i=n-c;i>=1;i--){
if(id[i]!=id[i+1])nx[i]=0;
else nx[i]=nx[i+1];nx[i]+=a[i];//,cerr<<nx[i]<<"\n";
}
t2.build(1,1,n-c);//cerr<<t2.ask(1,1,n-c,2,4).mx<<"\n";
for(int i=1;i<=n;i+=c){//cout<<t1.ask(1,1,n,i,i+c-1).mx<<"\n";
t3.ch(1,1,n/c,(i-1)/c+1,t1.ask(1,1,n,i,i+c-1).mx);
if(i<=n-1)t4.ch(1,1,n/c-1,(i-1)/c+1,t2.ask(1,1,n-c,i,i+c-1).mx);
}
int op,x,y;ll ans;
for(int i=1;i<=q;i++){
cin>>op>>x>>y;
if(op==1){
if(id[x]>1)t2.add(1,1,n-c,x-c,id[x]*c-c,y-a[x],0),
t4.ch(1,1,n/c-1,id[x]-1,t2.ask(1,1,n-c,id[x]*c-c-c+1,id[x]*c-c).mx);//,cout<<t2.ask(1,1,n-c,id[x]*c-c-c+1,id[x]*c-c).mx<<"\n";
if(id[x]<n/c)t2.add(1,1,n-c,id[x]*c-c+1,x,y-a[x],1),
t4.ch(1,1,n/c-1,id[x],t2.ask(1,1,n-c,id[x]*c-c+1,id[x]*c).mx);
t1.ch(1,1,n,x,y);a[x]=y;
t3.ch(1,1,n/c,id[x],t1.ask(1,1,n,id[x]*c-c+1,id[x]*c).mx);
}
else{ans=0;//if(c==5)cout<<x<<" "<<y<<"\n";
if(y-x+1<=c)ans=max(ans,t1.ask(1,1,n,x,y).mx);
else if(id[x]==id[y]-1){
ans=max(ans,t2.ask(1,1,n-c,x,y-c).mx);//if(c==1)assert(ans==0);
ans=max(ans,t1.ask(1,1,n,x,x+c-1).mx);
ans=max(ans,t1.ask(1,1,n,y-c+1,y).mx);
}
else{
if(id[y]-id[x]>2){
ans=max(ans,t4.ask(1,1,n/c-1,id[x]+1,id[y]-2));
//if(c==1)assert(ans==0);
}
ans=max(ans,t3.ask(1,1,n/c,id[x]+1,id[y]-1));//cout<<ans<<'\n\n';
ans=max(ans,t2.ask(1,1,n-c,x,id[x]*c).mx);
// if(c==1)assert(t2.ask(1,1,n-c,x,id[x]*c).mx<0);
ans=max(ans,t1.ask(1,1,n,x,x+c-1).mx);
ans=max(ans,t2.ask(1,1,n-c,id[y]*c-c-c+1,y-c).mx);
// if(c==1)assert(t2.ask(1,1,n-c,id[y]*c-c+1,y).mx<0);
ans=max(ans,t1.ask(1,1,n,y-c+1,y).mx);
}
cout<<ans<<"\n";
}
}return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 13924kb
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: 874ms
memory: 58280kb
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: 804ms
memory: 56408kb
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 4322308420 3390067591 4544135313 4544135313 4322308420 4386413596 4386413596 3797111846 4322308420 4100474957 4266013548 4544135313 4386413596 4094787940 4386413596 4386413596 4386413596 4322308420 4266013548 4386413596 4322308420 4544135313 4386413596 4322308420 4322308420 385...
result:
wrong answer 3rd numbers differ - expected: '4443416295', found: '4322308420'