oj.uz

Submission #839237

# Submission time Handle Problem Language Result Execution time Memory
839237 2023-08-29T10:10:18 Z 8pete8 Progression (NOI20_progression) C++17
68 / 100
 837 ms 77956 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<cmath>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#define int long long
#define mod 1000000007
const int mxn=4*1e5,lg=20,inf=1e18;
int n,m;
struct node{
    int as=0,ms=1,ls=0,rs=0,lv=0,rv=0,sum=0;
    //all size, max size, left size,right size,left val,right val;
};
void print(node a){
    cout<<a.as<<" "<<a.ms<<" "<<a.ls<<" "<<a.rs<<" "<<a.lv<<" "<<a.rv<<'\n';
}
node seg[4*mxn+10];
int add[4*mxn+10],change[4*mxn+10],v[mxn+10];
int h;//height of tree
node comb(node a,node b){
    node tmp;
    if(a.rv==inf)return b;
    if(b.rv==inf)return a;
    tmp.ms=max(a.ms,b.ms);
    if(a.rv==b.lv)tmp.ms=max(tmp.ms,a.rs+b.ls);
    tmp.lv=a.lv;
    tmp.rv=b.rv;
    if(a.ls==a.as&&b.lv==a.lv)tmp.ls=a.ls+b.ls;
    if(b.rs==b.as&&a.rv==b.rv)tmp.rs=b.rs+a.rs;
    tmp.ls=max(tmp.ls,a.ls);
    tmp.rs=max(tmp.rs,b.rs);
    tmp.as=a.as+b.as;
    tmp.sum=a.sum+b.sum;
    return tmp;
}
void build(int pos,int l,int r){
   // cout<<pos<<" "<<l<<" "<<r<<'\n';
   if(r<l)return;
    if(l==r){
        seg[pos].as=seg[pos].ls=seg[pos].rs=seg[pos].ms=1;
        seg[pos].lv=seg[pos].rv=seg[pos].sum=v[l];
    }
    else{
        int mid=l+(r-l)/2;
        build(pos*2,l,mid);
        build(pos*2+1,mid+1,r);
        seg[pos]=comb(seg[pos<<1],seg[(pos<<1)|1]);
    }
}
void app(int pos){
    if(change[pos]){
        seg[pos].ms=seg[pos].ls=seg[pos].rs=seg[pos].as;
        seg[pos].lv=seg[pos].rv=change[pos];
        seg[pos].sum=seg[pos].as*change[pos];
    }
    if(add[pos]){
        seg[pos].lv+=add[pos];
        seg[pos].rv+=add[pos];
        seg[pos].sum+=(seg[pos].as*add[pos]);
    }
}
void push(int pos,int l,int r){
    if(add[pos]){
        app(pos);
        if(l!=r){
            add[pos*2]+=add[pos];
            add[pos*2+1]+=add[pos];
        }
    }
    if(change[pos]){
        app(pos);
        if(l!=r){
            add[pos*2]=0;
            add[pos*2+1]=0;
            change[pos*2]=change[pos];
            change[pos*2+1]=change[pos];
        }
    }
    add[pos]=0;
    change[pos]=0;
}
void update(int pos,int l,int r,int ql,int qr,int val){
    if(r<l)return;
    push(pos,l,r);
    //cout<<pos<<' '<<l<<" "<<r<<' '<<ql<<" "<<qr<<'\n';
    if(r<ql||l>qr)return;
    if(ql<=l&&r<=qr){
        add[pos]+=val;
        push(pos,l,r);
        return;
    }
    int mid=l+(r-l)/2;
    update(pos*2,l,mid,ql,qr,val);
    update(pos*2+1,mid+1,r,ql,qr,val);
    seg[pos]=comb(seg[pos*2],seg[pos*2+1]);
}
void update2(int pos,int l,int r,int ql,int qr,int val){
    if(r<l)return;
    if(r<ql||l>qr)return;
    //cout<<pos<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<val<<'\n';
    if(ql<=l&&r<=qr){
        change[pos]=val;
        add[pos]=0;
        push(pos,l,r);
        return;
    }
    push(pos,l,r);
    int mid=l+(r-l)/2;
    update2(pos*2,l,mid,ql,qr,val);
    update2(pos*2+1,mid+1,r,ql,qr,val);
    seg[pos]=comb(seg[pos<<1],seg[(pos<<1)|1]);
}
node query(int pos,int l,int r,int ql,int qr){
    node tmp;
    tmp.rv=inf;
    if(r<l)return tmp;
    if(r<ql||l>qr)return tmp;
    push(pos,l,r);
    if(ql<=l&&r<=qr)return seg[pos];
    int mid=l+(r-l)/2;
    if(l<=ql&&qr<=mid)return query(pos*2,l,mid,ql,qr);
    if(ql>=mid+1&&qr<=r)return query(pos*2+1,mid+1,r,ql,qr);
    return comb(query(pos*2,l,mid,ql,qr),query(pos*2+1,mid+1,r,ql,qr));
}
int32_t main(){
    fastio
    int n,m;cin>>n>>m;
    for(int i=0;i<n;i++)cin>>v[i];
    int val=v[0];
    n--;
    for(int i=0;i<n;i++)v[i]=v[i+1]-v[i];
    build(1,0,n-1);
    int diff;
    while(m--){
        int type;cin>>type;
        if(type==1){
            int l,r,x,c;cin>>l>>r>>x>>c;
            l--,r--;
            if(l)update(1,0,n-1,l-1,l-1,x);
            else val+=x;
            if(r<n)update(1,0,n-1,r,r,-((x+((r-l)*c))));
            if(l!=r)update(1,0,n-1,l,r-1,c);
        }
        else if(type==2){
            int l,r,x,c;cin>>l>>r>>x>>c;
            l--,r--;
            int suml,sumr;
            if(r<n){
                if(r)sumr=query(1,0,n-1,0,r-1).sum+val;
                else sumr=val;
                diff=sumr-(x+(r-l)*c);
                update(1,0,n-1,r,r,diff);
            }
            if(l){
                suml=query(1,0,n-1,0,l-1).sum+val;
                diff=x-suml;
                update(1,0,n-1,l-1,l-1,diff);
            }
            else val=x;
            if(l!=r)update2(1,0,n-1,l,r-1,c);
        }
        else{
            int l,r;cin>>l>>r;
            l--;
            r--;
            cout<<((l==r)?0:query(1,0,n-1,l,r-1).ms)+1<<'\n';
        }
    }
 
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 60748 KB Output is correct
2 Correct 63 ms 616 KB Output is correct
3 Correct 62 ms 588 KB Output is correct
4 Correct 61 ms 588 KB Output is correct
5 Correct 62 ms 712 KB Output is correct
6 Correct 61 ms 716 KB Output is correct
7 Correct 61 ms 580 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 157 ms 60752 KB Output is correct
12 Correct 126 ms 60600 KB Output is correct
13 Correct 127 ms 60908 KB Output is correct
14 Correct 124 ms 60908 KB Output is correct
15 Correct 126 ms 61004 KB Output is correct
16 Correct 136 ms 60624 KB Output is correct
17 Correct 128 ms 60688 KB Output is correct
18 Correct 135 ms 60608 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 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 257 ms 77516 KB Output is correct
2 Correct 69 ms 844 KB Output is correct
3 Correct 65 ms 844 KB Output is correct
4 Correct 59 ms 844 KB Output is correct
5 Correct 69 ms 968 KB Output is correct
6 Correct 69 ms 972 KB Output is correct
7 Correct 71 ms 972 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 317 ms 77260 KB Output is correct
12 Correct 255 ms 77636 KB Output is correct
13 Correct 329 ms 77472 KB Output is correct
14 Correct 333 ms 77428 KB Output is correct
15 Correct 281 ms 77472 KB Output is correct
16 Correct 307 ms 77900 KB Output is correct
17 Correct 305 ms 77900 KB Output is correct
18 Correct 316 ms 77956 KB Output is correct
19 Correct 262 ms 77160 KB Output is correct
20 Correct 255 ms 77244 KB Output is correct
21 Correct 255 ms 77276 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 76748 KB Output is correct
2 Correct 126 ms 460 KB Output is correct
3 Correct 137 ms 492 KB Output is correct
4 Correct 138 ms 456 KB Output is correct
5 Correct 132 ms 460 KB Output is correct
6 Correct 136 ms 528 KB Output is correct
7 Correct 132 ms 460 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 657 ms 76860 KB Output is correct
12 Correct 640 ms 76820 KB Output is correct
13 Correct 653 ms 76828 KB Output is correct
14 Correct 671 ms 76832 KB Output is correct
15 Correct 610 ms 76744 KB Output is correct
16 Correct 672 ms 76848 KB Output is correct
17 Correct 699 ms 76888 KB Output is correct
18 Correct 676 ms 76824 KB Output is correct
19 Correct 627 ms 76724 KB Output is correct
20 Correct 635 ms 76724 KB Output is correct
21 Correct 631 ms 76768 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 77516 KB Output is correct
2 Correct 69 ms 844 KB Output is correct
3 Correct 65 ms 844 KB Output is correct
4 Correct 59 ms 844 KB Output is correct
5 Correct 69 ms 968 KB Output is correct
6 Correct 69 ms 972 KB Output is correct
7 Correct 71 ms 972 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 317 ms 77260 KB Output is correct
12 Correct 255 ms 77636 KB Output is correct
13 Correct 329 ms 77472 KB Output is correct
14 Correct 333 ms 77428 KB Output is correct
15 Correct 281 ms 77472 KB Output is correct
16 Correct 307 ms 77900 KB Output is correct
17 Correct 305 ms 77900 KB Output is correct
18 Correct 316 ms 77956 KB Output is correct
19 Correct 262 ms 77160 KB Output is correct
20 Correct 255 ms 77244 KB Output is correct
21 Correct 255 ms 77276 KB Output is correct
22 Correct 733 ms 76928 KB Output is correct
23 Correct 131 ms 540 KB Output is correct
24 Correct 131 ms 580 KB Output is correct
25 Correct 127 ms 616 KB Output is correct
26 Correct 137 ms 536 KB Output is correct
27 Correct 137 ms 716 KB Output is correct
28 Correct 132 ms 588 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 763 ms 76980 KB Output is correct
33 Correct 706 ms 77004 KB Output is correct
34 Correct 780 ms 76872 KB Output is correct
35 Correct 765 ms 76872 KB Output is correct
36 Correct 622 ms 77208 KB Output is correct
37 Correct 646 ms 77148 KB Output is correct
38 Correct 627 ms 77200 KB Output is correct
39 Correct 751 ms 76944 KB Output is correct
40 Correct 837 ms 76924 KB Output is correct
41 Correct 794 ms 76924 KB Output is correct
42 Correct 763 ms 76960 KB Output is correct
43 Correct 766 ms 76904 KB Output is correct
44 Correct 719 ms 76872 KB Output is correct
45 Correct 739 ms 77008 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 60748 KB Output is correct
2 Correct 63 ms 616 KB Output is correct
3 Correct 62 ms 588 KB Output is correct
4 Correct 61 ms 588 KB Output is correct
5 Correct 62 ms 712 KB Output is correct
6 Correct 61 ms 716 KB Output is correct
7 Correct 61 ms 580 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 157 ms 60752 KB Output is correct
12 Correct 126 ms 60600 KB Output is correct
13 Correct 127 ms 60908 KB Output is correct
14 Correct 124 ms 60908 KB Output is correct
15 Correct 126 ms 61004 KB Output is correct
16 Correct 136 ms 60624 KB Output is correct
17 Correct 128 ms 60688 KB Output is correct
18 Correct 135 ms 60608 KB Output is correct
19 Incorrect 2 ms 468 KB Output isn't correct
20 Halted 0 ms 0 KB -