oj.uz

Submission #901611

# Submission time Handle Problem Language Result Execution time Memory
901611 2024-01-09T16:53:26 Z imarn Progression (NOI20_progression) C++14
68 / 100
 747 ms 98820 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#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];
ll a[N];
pii lz[4*N];
bool lzc[4*N]{0};
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 clr(int i,int l,int r){
    if(lzc[i]){
        lz[i]={0,0};
        t[i]={0,0,r-l+1,r-l+1,r-l+1,r-l+1,0,0};
        if(l<r){
            lzc[2*i]=lzc[2*i+1]=lzc[i];
        }lzc[i]=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){
    clr(i,l,r);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,ll S,ll L,ll C){
    clr(i,l,r);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];
}
void setzero(int i,int l,int r,int tl,int tr){
    clr(i,l,r);push(i,l,r);
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        lzc[i]=1;clr(i,l,r);return;
    }int m=(l+r)>>1;
    setzero(2*i,l,m,tl,tr);setzero(2*i+1,m+1,r,tl,tr);
    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){
            ll l,r,s,c;cin>>l>>r>>s>>c;
            upd(1,1,n,l,r,s,l,c);
        }
        if(x==2){
            ll l,r,s,c;cin>>l>>r>>s>>c;
            setzero(1,1,n,l,r);
            upd(1,1,n,l,r,s,l,c);
        }
        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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 89172 KB Output is correct
2 Correct 68 ms 26244 KB Output is correct
3 Correct 72 ms 26192 KB Output is correct
4 Correct 69 ms 26080 KB Output is correct
5 Correct 70 ms 26192 KB Output is correct
6 Correct 69 ms 26068 KB Output is correct
7 Correct 69 ms 26196 KB Output is correct
8 Correct 4 ms 22876 KB Output is correct
9 Correct 3 ms 22876 KB Output is correct
10 Correct 3 ms 22872 KB Output is correct
11 Correct 118 ms 97144 KB Output is correct
12 Correct 118 ms 97108 KB Output is correct
13 Correct 118 ms 97416 KB Output is correct
14 Correct 117 ms 97620 KB Output is correct
15 Correct 117 ms 97360 KB Output is correct
16 Correct 118 ms 97220 KB Output is correct
17 Correct 119 ms 97044 KB Output is correct
18 Correct 118 ms 97116 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 22876 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 320 ms 89684 KB Output is correct
2 Correct 91 ms 23376 KB Output is correct
3 Correct 95 ms 24124 KB Output is correct
4 Correct 91 ms 23376 KB Output is correct
5 Correct 93 ms 23468 KB Output is correct
6 Correct 94 ms 23660 KB Output is correct
7 Correct 97 ms 23888 KB Output is correct
8 Correct 3 ms 22872 KB Output is correct
9 Correct 3 ms 22876 KB Output is correct
10 Correct 3 ms 22876 KB Output is correct
11 Correct 368 ms 89472 KB Output is correct
12 Correct 315 ms 89772 KB Output is correct
13 Correct 361 ms 89340 KB Output is correct
14 Correct 371 ms 89480 KB Output is correct
15 Correct 324 ms 89680 KB Output is correct
16 Correct 376 ms 90272 KB Output is correct
17 Correct 367 ms 89940 KB Output is correct
18 Correct 374 ms 90196 KB Output is correct
19 Correct 325 ms 89380 KB Output is correct
20 Correct 338 ms 89328 KB Output is correct
21 Correct 328 ms 89172 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 89132 KB Output is correct
2 Correct 134 ms 26192 KB Output is correct
3 Correct 136 ms 26140 KB Output is correct
4 Correct 133 ms 26192 KB Output is correct
5 Correct 136 ms 26184 KB Output is correct
6 Correct 137 ms 26268 KB Output is correct
7 Correct 160 ms 26368 KB Output is correct
8 Correct 3 ms 22872 KB Output is correct
9 Correct 4 ms 22876 KB Output is correct
10 Correct 4 ms 22876 KB Output is correct
11 Correct 534 ms 95184 KB Output is correct
12 Correct 525 ms 98380 KB Output is correct
13 Correct 538 ms 95180 KB Output is correct
14 Correct 533 ms 95316 KB Output is correct
15 Correct 502 ms 98256 KB Output is correct
16 Correct 550 ms 98772 KB Output is correct
17 Correct 546 ms 98820 KB Output is correct
18 Correct 543 ms 98528 KB Output is correct
19 Correct 547 ms 98448 KB Output is correct
20 Correct 525 ms 98624 KB Output is correct
21 Correct 517 ms 98484 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 89684 KB Output is correct
2 Correct 91 ms 23376 KB Output is correct
3 Correct 95 ms 24124 KB Output is correct
4 Correct 91 ms 23376 KB Output is correct
5 Correct 93 ms 23468 KB Output is correct
6 Correct 94 ms 23660 KB Output is correct
7 Correct 97 ms 23888 KB Output is correct
8 Correct 3 ms 22872 KB Output is correct
9 Correct 3 ms 22876 KB Output is correct
10 Correct 3 ms 22876 KB Output is correct
11 Correct 368 ms 89472 KB Output is correct
12 Correct 315 ms 89772 KB Output is correct
13 Correct 361 ms 89340 KB Output is correct
14 Correct 371 ms 89480 KB Output is correct
15 Correct 324 ms 89680 KB Output is correct
16 Correct 376 ms 90272 KB Output is correct
17 Correct 367 ms 89940 KB Output is correct
18 Correct 374 ms 90196 KB Output is correct
19 Correct 325 ms 89380 KB Output is correct
20 Correct 338 ms 89328 KB Output is correct
21 Correct 328 ms 89172 KB Output is correct
22 Correct 587 ms 89000 KB Output is correct
23 Correct 120 ms 23076 KB Output is correct
24 Correct 123 ms 23484 KB Output is correct
25 Correct 119 ms 23336 KB Output is correct
26 Correct 121 ms 23104 KB Output is correct
27 Correct 124 ms 23120 KB Output is correct
28 Correct 129 ms 23324 KB Output is correct
29 Correct 3 ms 22876 KB Output is correct
30 Correct 4 ms 22876 KB Output is correct
31 Correct 3 ms 22876 KB Output is correct
32 Correct 654 ms 89080 KB Output is correct
33 Correct 634 ms 89104 KB Output is correct
34 Correct 684 ms 92296 KB Output is correct
35 Correct 747 ms 92320 KB Output is correct
36 Correct 633 ms 92412 KB Output is correct
37 Correct 637 ms 92452 KB Output is correct
38 Correct 636 ms 92276 KB Output is correct
39 Correct 675 ms 93568 KB Output is correct
40 Correct 701 ms 93804 KB Output is correct
41 Correct 720 ms 93960 KB Output is correct
42 Correct 684 ms 93768 KB Output is correct
43 Correct 620 ms 93816 KB Output is correct
44 Correct 608 ms 93604 KB Output is correct
45 Correct 602 ms 93524 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 89172 KB Output is correct
2 Correct 68 ms 26244 KB Output is correct
3 Correct 72 ms 26192 KB Output is correct
4 Correct 69 ms 26080 KB Output is correct
5 Correct 70 ms 26192 KB Output is correct
6 Correct 69 ms 26068 KB Output is correct
7 Correct 69 ms 26196 KB Output is correct
8 Correct 4 ms 22876 KB Output is correct
9 Correct 3 ms 22876 KB Output is correct
10 Correct 3 ms 22872 KB Output is correct
11 Correct 118 ms 97144 KB Output is correct
12 Correct 118 ms 97108 KB Output is correct
13 Correct 118 ms 97416 KB Output is correct
14 Correct 117 ms 97620 KB Output is correct
15 Correct 117 ms 97360 KB Output is correct
16 Correct 118 ms 97220 KB Output is correct
17 Correct 119 ms 97044 KB Output is correct
18 Correct 118 ms 97116 KB Output is correct
19 Incorrect 5 ms 22876 KB Output isn't correct
20 Halted 0 ms 0 KB -