oj.uz

Submission #799716

# Submission time Handle Problem Language Result Execution time Memory
799716 2023-07-31T20:51:15 Z ttamx Progression (NOI20_progression) C++14
57 / 100
 857 ms 96316 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.update2(l,l,a-le);
            s.update2(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 800 ms 79472 KB Output is correct
2 Correct 191 ms 69248 KB Output is correct
3 Correct 166 ms 69236 KB Output is correct
4 Correct 164 ms 69196 KB Output is correct
5 Correct 169 ms 69260 KB Output is correct
6 Correct 167 ms 69248 KB Output is correct
7 Correct 171 ms 69172 KB Output is correct
8 Correct 26 ms 65996 KB Output is correct
9 Correct 29 ms 66004 KB Output is correct
10 Correct 27 ms 66004 KB Output is correct
11 Correct 805 ms 79328 KB Output is correct
12 Correct 801 ms 79368 KB Output is correct
13 Correct 801 ms 79584 KB Output is correct
14 Correct 824 ms 79692 KB Output is correct
15 Correct 810 ms 79532 KB Output is correct
16 Correct 800 ms 79320 KB Output is correct
17 Correct 779 ms 79324 KB Output is correct
18 Correct 857 ms 78036 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 65980 KB Output is correct
2 Incorrect 28 ms 66004 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 93204 KB Output is correct
2 Correct 128 ms 68696 KB Output is correct
3 Correct 103 ms 68600 KB Output is correct
4 Correct 85 ms 68688 KB Output is correct
5 Correct 150 ms 68780 KB Output is correct
6 Correct 148 ms 68848 KB Output is correct
7 Correct 120 ms 68776 KB Output is correct
8 Correct 25 ms 65956 KB Output is correct
9 Correct 24 ms 65916 KB Output is correct
10 Correct 28 ms 65976 KB Output is correct
11 Correct 392 ms 93224 KB Output is correct
12 Correct 377 ms 93220 KB Output is correct
13 Correct 414 ms 92660 KB Output is correct
14 Correct 368 ms 92604 KB Output is correct
15 Correct 379 ms 92548 KB Output is correct
16 Correct 377 ms 92568 KB Output is correct
17 Correct 344 ms 92396 KB Output is correct
18 Correct 425 ms 92460 KB Output is correct
19 Correct 296 ms 91708 KB Output is correct
20 Correct 308 ms 91424 KB Output is correct
21 Correct 298 ms 91336 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 91412 KB Output is correct
2 Incorrect 177 ms 68640 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 357 ms 93204 KB Output is correct
2 Correct 128 ms 68696 KB Output is correct
3 Correct 103 ms 68600 KB Output is correct
4 Correct 85 ms 68688 KB Output is correct
5 Correct 150 ms 68780 KB Output is correct
6 Correct 148 ms 68848 KB Output is correct
7 Correct 120 ms 68776 KB Output is correct
8 Correct 25 ms 65956 KB Output is correct
9 Correct 24 ms 65916 KB Output is correct
10 Correct 28 ms 65976 KB Output is correct
11 Correct 392 ms 93224 KB Output is correct
12 Correct 377 ms 93220 KB Output is correct
13 Correct 414 ms 92660 KB Output is correct
14 Correct 368 ms 92604 KB Output is correct
15 Correct 379 ms 92548 KB Output is correct
16 Correct 377 ms 92568 KB Output is correct
17 Correct 344 ms 92396 KB Output is correct
18 Correct 425 ms 92460 KB Output is correct
19 Correct 296 ms 91708 KB Output is correct
20 Correct 308 ms 91424 KB Output is correct
21 Correct 298 ms 91336 KB Output is correct
22 Correct 686 ms 90608 KB Output is correct
23 Correct 149 ms 68736 KB Output is correct
24 Correct 148 ms 68536 KB Output is correct
25 Correct 179 ms 68488 KB Output is correct
26 Correct 157 ms 68712 KB Output is correct
27 Correct 152 ms 68796 KB Output is correct
28 Correct 146 ms 68896 KB Output is correct
29 Correct 31 ms 65992 KB Output is correct
30 Correct 34 ms 65988 KB Output is correct
31 Correct 28 ms 66008 KB Output is correct
32 Correct 729 ms 91228 KB Output is correct
33 Correct 664 ms 91052 KB Output is correct
34 Correct 702 ms 91248 KB Output is correct
35 Correct 807 ms 91516 KB Output is correct
36 Correct 563 ms 92092 KB Output is correct
37 Correct 575 ms 92392 KB Output is correct
38 Correct 610 ms 92972 KB Output is correct
39 Correct 769 ms 93356 KB Output is correct
40 Correct 755 ms 93776 KB Output is correct
41 Correct 719 ms 94000 KB Output is correct
42 Correct 801 ms 94668 KB Output is correct
43 Correct 662 ms 95552 KB Output is correct
44 Correct 679 ms 95652 KB Output is correct
45 Correct 734 ms 96316 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 79472 KB Output is correct
2 Correct 191 ms 69248 KB Output is correct
3 Correct 166 ms 69236 KB Output is correct
4 Correct 164 ms 69196 KB Output is correct
5 Correct 169 ms 69260 KB Output is correct
6 Correct 167 ms 69248 KB Output is correct
7 Correct 171 ms 69172 KB Output is correct
8 Correct 26 ms 65996 KB Output is correct
9 Correct 29 ms 66004 KB Output is correct
10 Correct 27 ms 66004 KB Output is correct
11 Correct 805 ms 79328 KB Output is correct
12 Correct 801 ms 79368 KB Output is correct
13 Correct 801 ms 79584 KB Output is correct
14 Correct 824 ms 79692 KB Output is correct
15 Correct 810 ms 79532 KB Output is correct
16 Correct 800 ms 79320 KB Output is correct
17 Correct 779 ms 79324 KB Output is correct
18 Correct 857 ms 78036 KB Output is correct
19 Correct 35 ms 65980 KB Output is correct
20 Incorrect 28 ms 66004 KB Output isn't correct
21 Halted 0 ms 0 KB -