oj.uz

Submission #901605

# Submission time Handle Problem Language Result Execution time Memory
901605 2024-01-09T16:44:24 Z imarn Progression (NOI20_progression) C++14
35 / 100
 538 ms 85172 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=3e5+5;
struct node{
    ll al,ar,mxl,mxr,mx,sz,dl,dr;
    node operator+(node b){
        node tmp;tmp.al=al;tmp.ar=b.ar;tmp.sz=sz+b.sz;
        tmp.mxl=max(mxl,1ll*2);tmp.mx=max({mx,b.mx,1ll*2});
        tmp.mxr=max(b.mxr,1ll*2);
        if(sz==0&&b.sz==0)return {0,0,0,0,0,0,0};
        else if(sz==0)return b;
        else if(b.sz==0)return {al,ar,mxl,mxr,mx,sz,dl,dr};
        else if(sz==1&&b.sz==1){
            tmp.mxl=2;tmp.mxr=2;tmp.mx=2;
            tmp.dl=b.al-ar,tmp.dr=b.al-ar;
        }
        else if(sz==1){
            if(b.al-ar==b.dl)tmp.mxl = max(tmp.mxl,1+b.mxl);
            if(b.al-ar==b.dl&&b.mxr==b.sz)tmp.mxr=max(tmp.mxr,1+b.mxr);
            if(b.al-ar==b.dl)tmp.mx=max(tmp.mx,1+b.mxl);
            tmp.dr=b.dr;tmp.dl=b.al-ar;
        }
        else if(b.sz==1){
            if(b.al-ar==dr&&mxl==sz)tmp.mxl = max({tmp.mxl,mxl+1});
            if(b.al-ar==dr)tmp.mxr=max(tmp.mxr,1+mxr);
            if(b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+1);
            tmp.dr=b.al-ar;tmp.dl=dl;
        }
        else {
            if(dr==b.dl&&b.al-ar==dr&&mxl==sz)tmp.mxl = max({tmp.mxl,mxl+b.mxl});
            if(dr==b.dl&&b.al-ar==dr&&b.mxr==b.sz)tmp.mxr=max({tmp.mxr,mxr+b.mxr});
            if(dr==b.dl&&b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+b.mxl);tmp.dl=dl,tmp.dr=b.dr;
            if(b.al-ar==dr&&mxl==sz)tmp.mxl = max({tmp.mxl,mxl+1});
            if(b.al-ar==b.dl&&b.mxr==b.sz)tmp.mxr=max({tmp.mxr,b.mxr+1});
            if(b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+1);
            if(b.al-ar==b.dl)tmp.mx=max(tmp.mx,b.mxl+1);
        }return tmp;
    }
}t[4*N];
int a[N];
pii lz[4*N];
void push(int i,int l,int r){
    t[i].al+=lz[i].f+l*lz[i].s;
    t[i].ar+=lz[i].f+r*lz[i].s;
    t[i].dl+=lz[i].s;t[i].dr+=lz[i].s;
    if(l<r){
        lz[2*i].f+=lz[i].f;lz[2*i].s+=lz[i].s;
        lz[2*i+1].f+=lz[i].f;lz[2*i+1].s+=lz[i].s;
    }lz[i]={0,0};
}
void build(int i,int l,int r){
    if(l==r)return void(t[i]={a[l],a[l],1,1,1,1,0,0});
    int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r);
    t[i]=t[2*i]+t[2*i+1];
}
node qr(int i,int l,int r,int tl,int tr){
    push(i,l,r);
    if(r<tl||l>tr)return {0,0,0,0,0,0,0,0};
    if(r<=tr&&l>=tl)return t[i];
    int m=(l+r)>>1;
    return qr(2*i,l,m,tl,tr)+qr(2*i+1,m+1,r,tl,tr);
}
void upd(int i,int l,int r,int tl,int tr,int S,int L,int C){
    push(i,l,r);
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        lz[i].f+=S-L*C;lz[i].s+=C;push(i,l,r);
        return;
    }int m=(l+r)>>1;
    upd(2*i,l,m,tl,tr,S,L,C);upd(2*i+1,m+1,r,tl,tr,S,L,C);
    t[i]=t[2*i]+t[2*i+1];
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<4*N;i++)lz[i]={0,0};
    build(1,1,n);
    while(q--){
        int x;cin>>x;
        if(x==1){
            int l,r,s,c;cin>>l>>r>>s>>c;
            upd(1,1,n,l,r,s,l,c);
        }
        if(x==2){
            int l,r,s,c;cin>>l>>r>>s>>c;continue;
        }
        if(x==3){
            int l,r;cin>>l>>r;
            cout<<qr(1,1,n,l,r).mx<<'\n';
        }
    }
}

Compilation message

Progression.cpp: In member function 'node node::operator+(node)':
Progression.cpp:38:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |             if(dr==b.dl&&b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+b.mxl);tmp.dl=dl,tmp.dr=b.dr;
      |             ^~
Progression.cpp:38:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |             if(dr==b.dl&&b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+b.mxl);tmp.dl=dl,tmp.dr=b.dr;
      |                                                                   ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 84204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 83224 KB Output is correct
2 Correct 105 ms 14932 KB Output is correct
3 Correct 95 ms 15000 KB Output is correct
4 Correct 97 ms 15436 KB Output is correct
5 Correct 94 ms 14932 KB Output is correct
6 Correct 93 ms 14932 KB Output is correct
7 Correct 92 ms 14672 KB Output is correct
8 Correct 4 ms 13144 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 350 ms 82168 KB Output is correct
12 Correct 304 ms 83224 KB Output is correct
13 Correct 335 ms 82076 KB Output is correct
14 Correct 348 ms 82316 KB Output is correct
15 Correct 295 ms 82804 KB Output is correct
16 Correct 348 ms 83488 KB Output is correct
17 Correct 343 ms 83068 KB Output is correct
18 Correct 355 ms 83144 KB Output is correct
19 Correct 312 ms 82476 KB Output is correct
20 Correct 314 ms 82772 KB Output is correct
21 Correct 310 ms 82524 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 357 ms 85172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 83224 KB Output is correct
2 Correct 105 ms 14932 KB Output is correct
3 Correct 95 ms 15000 KB Output is correct
4 Correct 97 ms 15436 KB Output is correct
5 Correct 94 ms 14932 KB Output is correct
6 Correct 93 ms 14932 KB Output is correct
7 Correct 92 ms 14672 KB Output is correct
8 Correct 4 ms 13144 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 350 ms 82168 KB Output is correct
12 Correct 304 ms 83224 KB Output is correct
13 Correct 335 ms 82076 KB Output is correct
14 Correct 348 ms 82316 KB Output is correct
15 Correct 295 ms 82804 KB Output is correct
16 Correct 348 ms 83488 KB Output is correct
17 Correct 343 ms 83068 KB Output is correct
18 Correct 355 ms 83144 KB Output is correct
19 Correct 312 ms 82476 KB Output is correct
20 Correct 314 ms 82772 KB Output is correct
21 Correct 310 ms 82524 KB Output is correct
22 Incorrect 538 ms 84268 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 84204 KB Output isn't correct
2 Halted 0 ms 0 KB -