oj.uz

Submission #799707

# Submission time Handle Problem Language Result Execution time Memory
799707 2023-07-31T20:41:43 Z ttamx Progression (NOI20_progression) C++14
57 / 100
 647 ms 89724 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> p2;

const int N=3e5+5;
const int K=1<<20;

int n,q;
ll a[N],b[N];

struct segtree{
    struct node{
        ll sz,ans,all,sum;
        p2 pre,suf;
        node(ll x=0):sz(1),pre(p2(1,x)),suf(p2(1,x)),all(1),ans(1),sum(x){}
        friend node operator+(node a,node b){
            node c;
            bool ok=(a.suf.second==b.pre.second);
            bool oka=(a.suf.first==a.sz);
            bool okb=(b.pre.first==b.sz);
            c.sz=a.sz+b.sz;
            c.sum=a.sum+b.sum;
            if(ok&&oka){
                c.pre=b.pre;
                c.pre.first+=a.sz;
            }else{
                c.pre=a.pre;
            }
            if(ok&&okb){
                c.suf=a.suf;
                c.suf.first+=b.sz;
            }else{
                c.suf=b.suf;
            }
            if(ok&&oka&&okb){
                c.all=a.sz+b.sz;
            }else{
                c.all=0;
            }
            c.ans=max(a.ans,b.ans);
            if(ok){
                c.ans=max(c.ans,a.suf.first+b.pre.first);
            }
            return c;
        }
    }t[K];
    ll lz[K],lz2[K];
    bool islz[K];
    void pushlz(int l,int r,int i){
        if(islz[i]){
            t[i].all=t[i].ans=t[i].sz;
            t[i].sum=t[i].sz*(lz[i]+lz2[i]);
            t[i].pre=t[i].suf=p2(t[i].sz,lz[i]+lz2[i]);
            if(l<r){
                lz[i*2]=lz[i*2+1]=lz[i];
                lz2[i*2]=lz2[i*2+1]=lz2[i];
                islz[i*2]=islz[i*2+1]=true;
            }
        }else{
            t[i].sum+=t[i].sz*lz[i];
            t[i].pre.second+=lz[i];
            t[i].suf.second+=lz[i];
            if(l<r){
                lz[i*2]+=lz[i];
                lz[i*2+1]+=lz[i];
            }
        }
        lz[i]=0;
        islz[i]=false;
    }
    void build(int l,int r,int i){
        if(l==r)return void(t[i]=b[l]);
        int m=(l+r)/2;
        build(l,m,i*2);
        build(m+1,r,i*2+1);
        t[i]=t[i*2]+t[i*2+1];
    }
    void build(){
        build(1,n+1,1);
    }
    void update(int l,int r,int i,int x,int y,ll v){
        pushlz(l,r,i);
        if(y<l||r<x)return;
        if(x<=l&&r<=y)return lz[i]=v,pushlz(l,r,i),void();
        int m=(l+r)/2;
        update(l,m,i*2,x,y,v);
        update(m+1,r,i*2+1,x,y,v);
        t[i]=t[i*2]+t[i*2+1];
    }
    void update(int x,int y,ll v){
        update(1,n+1,1,x,y,v);
    }
    void update2(int l,int r,int i,int x,int y,ll v){
        pushlz(l,r,i);
        if(y<l||r<x)return;
        if(x<=l&&r<=y)return islz[i]=true,lz2[i]=v,pushlz(l,r,i),void();
        int m=(l+r)/2;
        update2(l,m,i*2,x,y,v);
        update2(m+1,r,i*2+1,x,y,v);
        t[i]=t[i*2]+t[i*2+1];
    }
    void update2(int x,int y,ll v){
        update2(1,n+1,1,x,y,v);
    }
    node query(int l,int r,int i,int x,int y){
        pushlz(l,r,i);
        if(x<=l&&r<=y)return t[i];
        int m=(l+r)/2;
        if(x<=m&&m<y)return query(l,m,i*2,x,y)+query(m+1,r,i*2+1,x,y);
        if(x<=m)return query(l,m,i*2,x,y);
        else return query(m+1,r,i*2+1,x,y);
    }
    node query(int x,int y){
        return query(1,n+1,1,x,y);
    }
}s;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> q;
    for(int i=1;i<=n;i++)cin >> a[i];
    for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
    s.build();
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            ll l,r,a,b;
            cin >> l >> r >> a >> b;
            s.update(l,l,a);
            s.update(l+1,r,b);
            s.update(r+1,r+1,-a-(r-l)*b);
        }else if(t==2){
            ll l,r,a,b;
            cin >> l >> r >> a >> b;
            ll le=s.query(1,l).sum;
            ll ri=s.query(1,r+1).sum;
            s.update(l,l,a-le);
            s.update(r+1,r+1,ri-a-(r-l)*b);
            s.update2(l+1,r,b);
        }else{
            ll l,r;
            cin >> l >> r;
            cout << (l==r?0:s.query(l+1,r).ans)+1 << "\n";
        }
    }
}

Compilation message

Progression.cpp: In constructor 'segtree::node::node(ll)':
Progression.cpp:17:16: warning: 'segtree::node::suf' will be initialized after [-Wreorder]
   17 |         p2 pre,suf;
      |                ^~~
Progression.cpp:16:19: warning:   'll segtree::node::all' [-Wreorder]
   16 |         ll sz,ans,all,sum;
      |                   ^~~
Progression.cpp:18:9: warning:   when initialized here [-Wreorder]
   18 |         node(ll x=0):sz(1),pre(p2(1,x)),suf(p2(1,x)),all(1),ans(1),sum(x){}
      |         ^~~~
Progression.cpp:16:19: warning: 'segtree::node::all' will be initialized after [-Wreorder]
   16 |         ll sz,ans,all,sum;
      |                   ^~~
Progression.cpp:16:15: warning:   'll segtree::node::ans' [-Wreorder]
   16 |         ll sz,ans,all,sum;
      |               ^~~
Progression.cpp:18:9: warning:   when initialized here [-Wreorder]
   18 |         node(ll x=0):sz(1),pre(p2(1,x)),suf(p2(1,x)),all(1),ans(1),sum(x){}
      |         ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 79436 KB Output is correct
2 Correct 164 ms 69232 KB Output is correct
3 Correct 163 ms 69136 KB Output is correct
4 Correct 171 ms 69332 KB Output is correct
5 Correct 166 ms 69208 KB Output is correct
6 Correct 166 ms 69196 KB Output is correct
7 Correct 165 ms 69120 KB Output is correct
8 Correct 27 ms 66000 KB Output is correct
9 Correct 26 ms 65996 KB Output is correct
10 Correct 27 ms 65984 KB Output is correct
11 Correct 601 ms 79376 KB Output is correct
12 Correct 619 ms 79340 KB Output is correct
13 Correct 605 ms 79760 KB Output is correct
14 Correct 605 ms 79748 KB Output is correct
15 Correct 615 ms 79560 KB Output is correct
16 Correct 619 ms 79260 KB Output is correct
17 Correct 625 ms 79272 KB Output is correct
18 Correct 620 ms 79260 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 66004 KB Output is correct
2 Correct 26 ms 65920 KB Output is correct
3 Incorrect 25 ms 65888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 86896 KB Output is correct
2 Correct 96 ms 68632 KB Output is correct
3 Correct 93 ms 68672 KB Output is correct
4 Correct 86 ms 68680 KB Output is correct
5 Correct 103 ms 68812 KB Output is correct
6 Correct 99 ms 68812 KB Output is correct
7 Correct 98 ms 68808 KB Output is correct
8 Correct 26 ms 66012 KB Output is correct
9 Correct 26 ms 65996 KB Output is correct
10 Correct 27 ms 65892 KB Output is correct
11 Correct 307 ms 85716 KB Output is correct
12 Correct 280 ms 86988 KB Output is correct
13 Correct 330 ms 85528 KB Output is correct
14 Correct 294 ms 85604 KB Output is correct
15 Correct 287 ms 86912 KB Output is correct
16 Correct 300 ms 87444 KB Output is correct
17 Correct 305 ms 87492 KB Output is correct
18 Correct 307 ms 87532 KB Output is correct
19 Correct 268 ms 86904 KB Output is correct
20 Correct 278 ms 86908 KB Output is correct
21 Correct 273 ms 86924 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 89724 KB Output is correct
2 Incorrect 152 ms 69324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 86896 KB Output is correct
2 Correct 96 ms 68632 KB Output is correct
3 Correct 93 ms 68672 KB Output is correct
4 Correct 86 ms 68680 KB Output is correct
5 Correct 103 ms 68812 KB Output is correct
6 Correct 99 ms 68812 KB Output is correct
7 Correct 98 ms 68808 KB Output is correct
8 Correct 26 ms 66012 KB Output is correct
9 Correct 26 ms 65996 KB Output is correct
10 Correct 27 ms 65892 KB Output is correct
11 Correct 307 ms 85716 KB Output is correct
12 Correct 280 ms 86988 KB Output is correct
13 Correct 330 ms 85528 KB Output is correct
14 Correct 294 ms 85604 KB Output is correct
15 Correct 287 ms 86912 KB Output is correct
16 Correct 300 ms 87444 KB Output is correct
17 Correct 305 ms 87492 KB Output is correct
18 Correct 307 ms 87532 KB Output is correct
19 Correct 268 ms 86904 KB Output is correct
20 Correct 278 ms 86908 KB Output is correct
21 Correct 273 ms 86924 KB Output is correct
22 Correct 602 ms 89148 KB Output is correct
23 Correct 142 ms 69196 KB Output is correct
24 Correct 138 ms 69200 KB Output is correct
25 Correct 138 ms 69160 KB Output is correct
26 Correct 142 ms 69192 KB Output is correct
27 Correct 143 ms 69264 KB Output is correct
28 Correct 156 ms 69288 KB Output is correct
29 Correct 31 ms 65984 KB Output is correct
30 Correct 29 ms 65952 KB Output is correct
31 Correct 26 ms 65912 KB Output is correct
32 Correct 593 ms 86400 KB Output is correct
33 Correct 585 ms 89144 KB Output is correct
34 Correct 621 ms 86324 KB Output is correct
35 Correct 614 ms 86392 KB Output is correct
36 Correct 492 ms 86280 KB Output is correct
37 Correct 495 ms 86472 KB Output is correct
38 Correct 489 ms 86260 KB Output is correct
39 Correct 611 ms 89188 KB Output is correct
40 Correct 641 ms 89404 KB Output is correct
41 Correct 647 ms 89280 KB Output is correct
42 Correct 637 ms 89216 KB Output is correct
43 Correct 591 ms 89084 KB Output is correct
44 Correct 624 ms 89160 KB Output is correct
45 Correct 607 ms 89188 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 79436 KB Output is correct
2 Correct 164 ms 69232 KB Output is correct
3 Correct 163 ms 69136 KB Output is correct
4 Correct 171 ms 69332 KB Output is correct
5 Correct 166 ms 69208 KB Output is correct
6 Correct 166 ms 69196 KB Output is correct
7 Correct 165 ms 69120 KB Output is correct
8 Correct 27 ms 66000 KB Output is correct
9 Correct 26 ms 65996 KB Output is correct
10 Correct 27 ms 65984 KB Output is correct
11 Correct 601 ms 79376 KB Output is correct
12 Correct 619 ms 79340 KB Output is correct
13 Correct 605 ms 79760 KB Output is correct
14 Correct 605 ms 79748 KB Output is correct
15 Correct 615 ms 79560 KB Output is correct
16 Correct 619 ms 79260 KB Output is correct
17 Correct 625 ms 79272 KB Output is correct
18 Correct 620 ms 79260 KB Output is correct
19 Correct 26 ms 66004 KB Output is correct
20 Correct 26 ms 65920 KB Output is correct
21 Incorrect 25 ms 65888 KB Output isn't correct
22 Halted 0 ms 0 KB -