oj.uz

Submission #799693

# Submission time Handle Problem Language Result Execution time Memory
799693 2023-07-31T20:27:56 Z ttamx Progression (NOI20_progression) C++14
57 / 100
 643 ms 89764 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];
    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];
            t[i].pre=t[i].suf=p2(t[i].sz,lz[i]);
            if(l<r){
                lz[i*2]=lz[i];
                lz[i*2+1]=lz[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,lz[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 583 ms 79284 KB Output is correct
2 Correct 162 ms 69204 KB Output is correct
3 Correct 165 ms 69236 KB Output is correct
4 Correct 156 ms 69196 KB Output is correct
5 Correct 179 ms 69276 KB Output is correct
6 Correct 167 ms 69348 KB Output is correct
7 Correct 158 ms 69188 KB Output is correct
8 Correct 23 ms 65904 KB Output is correct
9 Correct 23 ms 65996 KB Output is correct
10 Correct 23 ms 66000 KB Output is correct
11 Correct 589 ms 79392 KB Output is correct
12 Correct 586 ms 79348 KB Output is correct
13 Correct 593 ms 79560 KB Output is correct
14 Correct 586 ms 79672 KB Output is correct
15 Correct 587 ms 79776 KB Output is correct
16 Correct 603 ms 79332 KB Output is correct
17 Correct 590 ms 79212 KB Output is correct
18 Correct 586 ms 79252 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65996 KB Output is correct
2 Correct 26 ms 65968 KB Output is correct
3 Incorrect 26 ms 65996 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 280 ms 86864 KB Output is correct
2 Correct 92 ms 68624 KB Output is correct
3 Correct 104 ms 68676 KB Output is correct
4 Correct 91 ms 68576 KB Output is correct
5 Correct 107 ms 68812 KB Output is correct
6 Correct 101 ms 68812 KB Output is correct
7 Correct 95 ms 68804 KB Output is correct
8 Correct 24 ms 65916 KB Output is correct
9 Correct 25 ms 65980 KB Output is correct
10 Correct 25 ms 65964 KB Output is correct
11 Correct 307 ms 85516 KB Output is correct
12 Correct 294 ms 86960 KB Output is correct
13 Correct 301 ms 85508 KB Output is correct
14 Correct 301 ms 85516 KB Output is correct
15 Correct 315 ms 87040 KB Output is correct
16 Correct 307 ms 87576 KB Output is correct
17 Correct 298 ms 87488 KB Output is correct
18 Correct 298 ms 87500 KB Output is correct
19 Correct 262 ms 86896 KB Output is correct
20 Correct 261 ms 86908 KB Output is correct
21 Correct 266 ms 86856 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 89764 KB Output is correct
2 Incorrect 156 ms 69344 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 280 ms 86864 KB Output is correct
2 Correct 92 ms 68624 KB Output is correct
3 Correct 104 ms 68676 KB Output is correct
4 Correct 91 ms 68576 KB Output is correct
5 Correct 107 ms 68812 KB Output is correct
6 Correct 101 ms 68812 KB Output is correct
7 Correct 95 ms 68804 KB Output is correct
8 Correct 24 ms 65916 KB Output is correct
9 Correct 25 ms 65980 KB Output is correct
10 Correct 25 ms 65964 KB Output is correct
11 Correct 307 ms 85516 KB Output is correct
12 Correct 294 ms 86960 KB Output is correct
13 Correct 301 ms 85508 KB Output is correct
14 Correct 301 ms 85516 KB Output is correct
15 Correct 315 ms 87040 KB Output is correct
16 Correct 307 ms 87576 KB Output is correct
17 Correct 298 ms 87488 KB Output is correct
18 Correct 298 ms 87500 KB Output is correct
19 Correct 262 ms 86896 KB Output is correct
20 Correct 261 ms 86908 KB Output is correct
21 Correct 266 ms 86856 KB Output is correct
22 Correct 608 ms 89276 KB Output is correct
23 Correct 139 ms 69228 KB Output is correct
24 Correct 146 ms 69224 KB Output is correct
25 Correct 137 ms 69184 KB Output is correct
26 Correct 141 ms 69228 KB Output is correct
27 Correct 143 ms 69196 KB Output is correct
28 Correct 137 ms 69200 KB Output is correct
29 Correct 30 ms 65984 KB Output is correct
30 Correct 30 ms 65968 KB Output is correct
31 Correct 24 ms 66004 KB Output is correct
32 Correct 643 ms 86404 KB Output is correct
33 Correct 584 ms 89088 KB Output is correct
34 Correct 596 ms 86344 KB Output is correct
35 Correct 608 ms 86448 KB Output is correct
36 Correct 492 ms 86216 KB Output is correct
37 Correct 485 ms 86268 KB Output is correct
38 Correct 481 ms 86220 KB Output is correct
39 Correct 596 ms 89308 KB Output is correct
40 Correct 604 ms 89276 KB Output is correct
41 Correct 607 ms 89236 KB Output is correct
42 Correct 637 ms 89156 KB Output is correct
43 Correct 592 ms 89216 KB Output is correct
44 Correct 587 ms 89164 KB Output is correct
45 Correct 576 ms 89200 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 79284 KB Output is correct
2 Correct 162 ms 69204 KB Output is correct
3 Correct 165 ms 69236 KB Output is correct
4 Correct 156 ms 69196 KB Output is correct
5 Correct 179 ms 69276 KB Output is correct
6 Correct 167 ms 69348 KB Output is correct
7 Correct 158 ms 69188 KB Output is correct
8 Correct 23 ms 65904 KB Output is correct
9 Correct 23 ms 65996 KB Output is correct
10 Correct 23 ms 66000 KB Output is correct
11 Correct 589 ms 79392 KB Output is correct
12 Correct 586 ms 79348 KB Output is correct
13 Correct 593 ms 79560 KB Output is correct
14 Correct 586 ms 79672 KB Output is correct
15 Correct 587 ms 79776 KB Output is correct
16 Correct 603 ms 79332 KB Output is correct
17 Correct 590 ms 79212 KB Output is correct
18 Correct 586 ms 79252 KB Output is correct
19 Correct 26 ms 65996 KB Output is correct
20 Correct 26 ms 65968 KB Output is correct
21 Incorrect 26 ms 65996 KB Output isn't correct
22 Halted 0 ms 0 KB -