oj.uz

Submission #901606

# Submission time Handle Problem Language Result Execution time Memory
901606 2024-01-09T16:45:33 Z imarn Progression (NOI20_progression) C++14
48 / 100
 639 ms 98324 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];
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,ll S,ll L,ll 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){
            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;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 111 ms 89332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 23132 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 377 ms 89660 KB Output is correct
2 Correct 91 ms 23636 KB Output is correct
3 Correct 92 ms 23636 KB Output is correct
4 Correct 98 ms 23672 KB Output is correct
5 Correct 92 ms 23708 KB Output is correct
6 Correct 92 ms 23636 KB Output is correct
7 Correct 93 ms 23632 KB Output is correct
8 Correct 3 ms 23132 KB Output is correct
9 Correct 3 ms 23132 KB Output is correct
10 Correct 4 ms 23132 KB Output is correct
11 Correct 355 ms 89588 KB Output is correct
12 Correct 312 ms 89936 KB Output is correct
13 Correct 369 ms 89596 KB Output is correct
14 Correct 354 ms 89864 KB Output is correct
15 Correct 319 ms 89792 KB Output is correct
16 Correct 363 ms 90152 KB Output is correct
17 Correct 366 ms 90192 KB Output is correct
18 Correct 375 ms 90592 KB Output is correct
19 Correct 314 ms 89428 KB Output is correct
20 Correct 329 ms 89680 KB Output is correct
21 Correct 329 ms 89432 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 89660 KB Output is correct
2 Correct 91 ms 23636 KB Output is correct
3 Correct 92 ms 23636 KB Output is correct
4 Correct 98 ms 23672 KB Output is correct
5 Correct 92 ms 23708 KB Output is correct
6 Correct 92 ms 23636 KB Output is correct
7 Correct 93 ms 23632 KB Output is correct
8 Correct 3 ms 23132 KB Output is correct
9 Correct 3 ms 23132 KB Output is correct
10 Correct 4 ms 23132 KB Output is correct
11 Correct 355 ms 89588 KB Output is correct
12 Correct 312 ms 89936 KB Output is correct
13 Correct 369 ms 89596 KB Output is correct
14 Correct 354 ms 89864 KB Output is correct
15 Correct 319 ms 89792 KB Output is correct
16 Correct 363 ms 90152 KB Output is correct
17 Correct 366 ms 90192 KB Output is correct
18 Correct 375 ms 90592 KB Output is correct
19 Correct 314 ms 89428 KB Output is correct
20 Correct 329 ms 89680 KB Output is correct
21 Correct 329 ms 89432 KB Output is correct
22 Correct 613 ms 89016 KB Output is correct
23 Correct 133 ms 26236 KB Output is correct
24 Correct 119 ms 26196 KB Output is correct
25 Correct 119 ms 26356 KB Output is correct
26 Correct 123 ms 26332 KB Output is correct
27 Correct 121 ms 26448 KB Output is correct
28 Correct 121 ms 26428 KB Output is correct
29 Correct 4 ms 23128 KB Output is correct
30 Correct 4 ms 23132 KB Output is correct
31 Correct 4 ms 23132 KB Output is correct
32 Correct 619 ms 95508 KB Output is correct
33 Correct 576 ms 98132 KB Output is correct
34 Correct 635 ms 95224 KB Output is correct
35 Correct 606 ms 95164 KB Output is correct
36 Correct 572 ms 95228 KB Output is correct
37 Correct 593 ms 95116 KB Output is correct
38 Correct 534 ms 95260 KB Output is correct
39 Correct 596 ms 97980 KB Output is correct
40 Correct 633 ms 98324 KB Output is correct
41 Correct 633 ms 98028 KB Output is correct
42 Correct 639 ms 97972 KB Output is correct
43 Correct 593 ms 97952 KB Output is correct
44 Correct 619 ms 97968 KB Output is correct
45 Correct 598 ms 98112 KB Output is correct

Subtask #6
0 / 17.0

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