oj.uz

Submission #799708

# Submission time Handle Problem Language Result Execution time Memory
799708 2023-07-31T20:42:28 Z ttamx Progression (NOI20_progression) C++14
57 / 100
 834 ms 97636 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]=lz2[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 788 ms 72168 KB Output is correct
2 Correct 188 ms 67108 KB Output is correct
3 Correct 172 ms 66960 KB Output is correct
4 Correct 167 ms 67144 KB Output is correct
5 Correct 171 ms 67352 KB Output is correct
6 Correct 171 ms 67532 KB Output is correct
7 Correct 167 ms 67668 KB Output is correct
8 Correct 35 ms 65928 KB Output is correct
9 Correct 28 ms 66016 KB Output is correct
10 Correct 30 ms 65920 KB Output is correct
11 Correct 818 ms 73312 KB Output is correct
12 Correct 809 ms 73248 KB Output is correct
13 Correct 799 ms 73592 KB Output is correct
14 Correct 802 ms 73588 KB Output is correct
15 Correct 794 ms 73516 KB Output is correct
16 Correct 806 ms 73856 KB Output is correct
17 Correct 803 ms 75244 KB Output is correct
18 Correct 834 ms 76520 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 66048 KB Output is correct
2 Correct 36 ms 65976 KB Output is correct
3 Incorrect 33 ms 65960 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 406 ms 95076 KB Output is correct
2 Correct 109 ms 68708 KB Output is correct
3 Correct 98 ms 68644 KB Output is correct
4 Correct 89 ms 68580 KB Output is correct
5 Correct 107 ms 68824 KB Output is correct
6 Correct 107 ms 68800 KB Output is correct
7 Correct 104 ms 68732 KB Output is correct
8 Correct 29 ms 65924 KB Output is correct
9 Correct 30 ms 65944 KB Output is correct
10 Correct 30 ms 66004 KB Output is correct
11 Correct 359 ms 93812 KB Output is correct
12 Correct 371 ms 95100 KB Output is correct
13 Correct 395 ms 93784 KB Output is correct
14 Correct 381 ms 93728 KB Output is correct
15 Correct 366 ms 95192 KB Output is correct
16 Correct 370 ms 95644 KB Output is correct
17 Correct 387 ms 95652 KB Output is correct
18 Correct 371 ms 95748 KB Output is correct
19 Correct 318 ms 95084 KB Output is correct
20 Correct 314 ms 95048 KB Output is correct
21 Correct 314 ms 95052 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 97024 KB Output is correct
2 Incorrect 154 ms 69244 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 406 ms 95076 KB Output is correct
2 Correct 109 ms 68708 KB Output is correct
3 Correct 98 ms 68644 KB Output is correct
4 Correct 89 ms 68580 KB Output is correct
5 Correct 107 ms 68824 KB Output is correct
6 Correct 107 ms 68800 KB Output is correct
7 Correct 104 ms 68732 KB Output is correct
8 Correct 29 ms 65924 KB Output is correct
9 Correct 30 ms 65944 KB Output is correct
10 Correct 30 ms 66004 KB Output is correct
11 Correct 359 ms 93812 KB Output is correct
12 Correct 371 ms 95100 KB Output is correct
13 Correct 395 ms 93784 KB Output is correct
14 Correct 381 ms 93728 KB Output is correct
15 Correct 366 ms 95192 KB Output is correct
16 Correct 370 ms 95644 KB Output is correct
17 Correct 387 ms 95652 KB Output is correct
18 Correct 371 ms 95748 KB Output is correct
19 Correct 318 ms 95084 KB Output is correct
20 Correct 314 ms 95048 KB Output is correct
21 Correct 314 ms 95052 KB Output is correct
22 Correct 723 ms 97304 KB Output is correct
23 Correct 145 ms 69156 KB Output is correct
24 Correct 143 ms 69136 KB Output is correct
25 Correct 140 ms 69196 KB Output is correct
26 Correct 153 ms 69328 KB Output is correct
27 Correct 150 ms 69232 KB Output is correct
28 Correct 152 ms 69232 KB Output is correct
29 Correct 30 ms 65940 KB Output is correct
30 Correct 29 ms 65960 KB Output is correct
31 Correct 29 ms 65984 KB Output is correct
32 Correct 655 ms 94592 KB Output is correct
33 Correct 690 ms 97292 KB Output is correct
34 Correct 678 ms 94612 KB Output is correct
35 Correct 661 ms 94716 KB Output is correct
36 Correct 527 ms 94396 KB Output is correct
37 Correct 545 ms 94368 KB Output is correct
38 Correct 525 ms 94500 KB Output is correct
39 Correct 658 ms 97412 KB Output is correct
40 Correct 660 ms 97636 KB Output is correct
41 Correct 686 ms 97524 KB Output is correct
42 Correct 690 ms 97480 KB Output is correct
43 Correct 624 ms 97492 KB Output is correct
44 Correct 635 ms 97308 KB Output is correct
45 Correct 651 ms 97504 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 72168 KB Output is correct
2 Correct 188 ms 67108 KB Output is correct
3 Correct 172 ms 66960 KB Output is correct
4 Correct 167 ms 67144 KB Output is correct
5 Correct 171 ms 67352 KB Output is correct
6 Correct 171 ms 67532 KB Output is correct
7 Correct 167 ms 67668 KB Output is correct
8 Correct 35 ms 65928 KB Output is correct
9 Correct 28 ms 66016 KB Output is correct
10 Correct 30 ms 65920 KB Output is correct
11 Correct 818 ms 73312 KB Output is correct
12 Correct 809 ms 73248 KB Output is correct
13 Correct 799 ms 73592 KB Output is correct
14 Correct 802 ms 73588 KB Output is correct
15 Correct 794 ms 73516 KB Output is correct
16 Correct 806 ms 73856 KB Output is correct
17 Correct 803 ms 75244 KB Output is correct
18 Correct 834 ms 76520 KB Output is correct
19 Correct 36 ms 66048 KB Output is correct
20 Correct 36 ms 65976 KB Output is correct
21 Incorrect 33 ms 65960 KB Output isn't correct
22 Halted 0 ms 0 KB -