QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#650109#5069. VacationsunkaihuanWA 874ms58280kbC++145.4kb2024-10-18 13:01:512024-10-18 13:01:52

Judging History

你现在查看的是最新测评结果

  • [2024-10-18 13:01:52]
  • 评测
  • 测评结果:WA
  • 用时:874ms
  • 内存:58280kb
  • [2024-10-18 13:01:51]
  • 提交

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'