oj.uz

Submission #839180

# Submission time Handle Problem Language Result Execution time Memory
839180 2023-08-29T01:54:51 Z 8pete8 Progression (NOI20_progression) C++14
68 / 100
 829 ms 86580 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){
                sumr=query(1,0,n-1,0,r-1).sum+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 128 ms 62772 KB Output is correct
2 Correct 63 ms 2636 KB Output is correct
3 Correct 63 ms 2700 KB Output is correct
4 Correct 75 ms 2656 KB Output is correct
5 Correct 69 ms 2792 KB Output is correct
6 Correct 64 ms 2636 KB Output is correct
7 Correct 63 ms 2648 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 464 KB Output is correct
11 Correct 131 ms 68716 KB Output is correct
12 Correct 135 ms 68568 KB Output is correct
13 Correct 130 ms 68940 KB Output is correct
14 Correct 142 ms 69124 KB Output is correct
15 Correct 138 ms 68948 KB Output is correct
16 Correct 135 ms 68648 KB Output is correct
17 Correct 134 ms 68556 KB Output is correct
18 Correct 134 ms 68620 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 568 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 262 ms 79608 KB Output is correct
2 Correct 70 ms 2892 KB Output is correct
3 Correct 73 ms 2892 KB Output is correct
4 Correct 60 ms 2892 KB Output is correct
5 Correct 71 ms 2988 KB Output is correct
6 Correct 75 ms 3144 KB Output is correct
7 Correct 89 ms 3020 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 326 ms 82252 KB Output is correct
12 Correct 264 ms 83660 KB Output is correct
13 Correct 329 ms 82216 KB Output is correct
14 Correct 330 ms 82260 KB Output is correct
15 Correct 263 ms 83532 KB Output is correct
16 Correct 318 ms 84320 KB Output is correct
17 Correct 322 ms 84156 KB Output is correct
18 Correct 322 ms 84192 KB Output is correct
19 Correct 269 ms 83496 KB Output is correct
20 Correct 255 ms 83476 KB Output is correct
21 Correct 268 ms 83488 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 78888 KB Output is correct
2 Correct 128 ms 2472 KB Output is correct
3 Correct 132 ms 3596 KB Output is correct
4 Correct 129 ms 3608 KB Output is correct
5 Correct 141 ms 3660 KB Output is correct
6 Correct 134 ms 3712 KB Output is correct
7 Correct 137 ms 3612 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 654 ms 83148 KB Output is correct
12 Correct 655 ms 86316 KB Output is correct
13 Correct 662 ms 83108 KB Output is correct
14 Correct 651 ms 83112 KB Output is correct
15 Correct 622 ms 86340 KB Output is correct
16 Correct 692 ms 86372 KB Output is correct
17 Correct 714 ms 86528 KB Output is correct
18 Correct 669 ms 86580 KB Output is correct
19 Correct 689 ms 86300 KB Output is correct
20 Correct 645 ms 86380 KB Output is correct
21 Correct 675 ms 86328 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 79608 KB Output is correct
2 Correct 70 ms 2892 KB Output is correct
3 Correct 73 ms 2892 KB Output is correct
4 Correct 60 ms 2892 KB Output is correct
5 Correct 71 ms 2988 KB Output is correct
6 Correct 75 ms 3144 KB Output is correct
7 Correct 89 ms 3020 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 326 ms 82252 KB Output is correct
12 Correct 264 ms 83660 KB Output is correct
13 Correct 329 ms 82216 KB Output is correct
14 Correct 330 ms 82260 KB Output is correct
15 Correct 263 ms 83532 KB Output is correct
16 Correct 318 ms 84320 KB Output is correct
17 Correct 322 ms 84156 KB Output is correct
18 Correct 322 ms 84192 KB Output is correct
19 Correct 269 ms 83496 KB Output is correct
20 Correct 255 ms 83476 KB Output is correct
21 Correct 268 ms 83488 KB Output is correct
22 Correct 750 ms 85932 KB Output is correct
23 Correct 133 ms 3488 KB Output is correct
24 Correct 128 ms 3532 KB Output is correct
25 Correct 133 ms 3684 KB Output is correct
26 Correct 137 ms 3576 KB Output is correct
27 Correct 135 ms 3548 KB Output is correct
28 Correct 135 ms 3532 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 771 ms 83056 KB Output is correct
33 Correct 751 ms 85860 KB Output is correct
34 Correct 789 ms 82968 KB Output is correct
35 Correct 779 ms 82952 KB Output is correct
36 Correct 641 ms 82852 KB Output is correct
37 Correct 636 ms 82852 KB Output is correct
38 Correct 675 ms 82916 KB Output is correct
39 Correct 770 ms 85836 KB Output is correct
40 Correct 829 ms 85912 KB Output is correct
41 Correct 787 ms 85868 KB Output is correct
42 Correct 828 ms 85832 KB Output is correct
43 Correct 743 ms 85848 KB Output is correct
44 Correct 750 ms 85832 KB Output is correct
45 Correct 778 ms 85828 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 62772 KB Output is correct
2 Correct 63 ms 2636 KB Output is correct
3 Correct 63 ms 2700 KB Output is correct
4 Correct 75 ms 2656 KB Output is correct
5 Correct 69 ms 2792 KB Output is correct
6 Correct 64 ms 2636 KB Output is correct
7 Correct 63 ms 2648 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 464 KB Output is correct
11 Correct 131 ms 68716 KB Output is correct
12 Correct 135 ms 68568 KB Output is correct
13 Correct 130 ms 68940 KB Output is correct
14 Correct 142 ms 69124 KB Output is correct
15 Correct 138 ms 68948 KB Output is correct
16 Correct 135 ms 68648 KB Output is correct
17 Correct 134 ms 68556 KB Output is correct
18 Correct 134 ms 68620 KB Output is correct
19 Incorrect 3 ms 568 KB Output isn't correct
20 Halted 0 ms 0 KB -