oj.uz

Submission #839032

# Submission time Handle Problem Language Result Execution time Memory
839032 2023-08-28T13:52:54 Z 8pete8 Progression (NOI20_progression) C++17
57 / 100
 783 ms 78048 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).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 131 ms 61108 KB Output is correct
2 Correct 63 ms 988 KB Output is correct
3 Correct 66 ms 964 KB Output is correct
4 Correct 62 ms 952 KB Output is correct
5 Correct 78 ms 1040 KB Output is correct
6 Correct 62 ms 1012 KB Output is correct
7 Correct 63 ms 972 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 129 ms 60940 KB Output is correct
12 Correct 132 ms 60876 KB Output is correct
13 Correct 150 ms 61224 KB Output is correct
14 Correct 128 ms 61184 KB Output is correct
15 Correct 134 ms 61260 KB Output is correct
16 Correct 126 ms 60872 KB Output is correct
17 Correct 126 ms 60860 KB Output is correct
18 Correct 138 ms 60880 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 260 ms 77900 KB Output is correct
2 Correct 71 ms 1268 KB Output is correct
3 Correct 67 ms 1236 KB Output is correct
4 Correct 62 ms 1304 KB Output is correct
5 Correct 72 ms 1324 KB Output is correct
6 Correct 70 ms 1400 KB Output is correct
7 Correct 69 ms 1352 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 314 ms 77376 KB Output is correct
12 Correct 263 ms 77560 KB Output is correct
13 Correct 333 ms 77276 KB Output is correct
14 Correct 331 ms 77272 KB Output is correct
15 Correct 280 ms 77500 KB Output is correct
16 Correct 321 ms 77848 KB Output is correct
17 Correct 357 ms 77900 KB Output is correct
18 Correct 319 ms 78048 KB Output is correct
19 Correct 267 ms 77260 KB Output is correct
20 Correct 256 ms 77264 KB Output is correct
21 Correct 248 ms 77260 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 76832 KB Output is correct
2 Incorrect 130 ms 680 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 260 ms 77900 KB Output is correct
2 Correct 71 ms 1268 KB Output is correct
3 Correct 67 ms 1236 KB Output is correct
4 Correct 62 ms 1304 KB Output is correct
5 Correct 72 ms 1324 KB Output is correct
6 Correct 70 ms 1400 KB Output is correct
7 Correct 69 ms 1352 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 314 ms 77376 KB Output is correct
12 Correct 263 ms 77560 KB Output is correct
13 Correct 333 ms 77276 KB Output is correct
14 Correct 331 ms 77272 KB Output is correct
15 Correct 280 ms 77500 KB Output is correct
16 Correct 321 ms 77848 KB Output is correct
17 Correct 357 ms 77900 KB Output is correct
18 Correct 319 ms 78048 KB Output is correct
19 Correct 267 ms 77260 KB Output is correct
20 Correct 256 ms 77264 KB Output is correct
21 Correct 248 ms 77260 KB Output is correct
22 Correct 753 ms 77004 KB Output is correct
23 Correct 131 ms 596 KB Output is correct
24 Correct 134 ms 572 KB Output is correct
25 Correct 133 ms 588 KB Output is correct
26 Correct 139 ms 716 KB Output is correct
27 Correct 134 ms 676 KB Output is correct
28 Correct 145 ms 716 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 780 ms 77052 KB Output is correct
33 Correct 751 ms 76964 KB Output is correct
34 Correct 762 ms 76984 KB Output is correct
35 Correct 782 ms 76968 KB Output is correct
36 Correct 639 ms 77252 KB Output is correct
37 Correct 628 ms 77380 KB Output is correct
38 Correct 636 ms 77200 KB Output is correct
39 Correct 776 ms 76928 KB Output is correct
40 Correct 780 ms 77004 KB Output is correct
41 Correct 766 ms 77004 KB Output is correct
42 Correct 783 ms 76964 KB Output is correct
43 Correct 743 ms 77004 KB Output is correct
44 Correct 744 ms 76948 KB Output is correct
45 Correct 736 ms 76904 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 61108 KB Output is correct
2 Correct 63 ms 988 KB Output is correct
3 Correct 66 ms 964 KB Output is correct
4 Correct 62 ms 952 KB Output is correct
5 Correct 78 ms 1040 KB Output is correct
6 Correct 62 ms 1012 KB Output is correct
7 Correct 63 ms 972 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 129 ms 60940 KB Output is correct
12 Correct 132 ms 60876 KB Output is correct
13 Correct 150 ms 61224 KB Output is correct
14 Correct 128 ms 61184 KB Output is correct
15 Correct 134 ms 61260 KB Output is correct
16 Correct 126 ms 60872 KB Output is correct
17 Correct 126 ms 60860 KB Output is correct
18 Correct 138 ms 60880 KB Output is correct
19 Incorrect 2 ms 468 KB Output isn't correct
20 Halted 0 ms 0 KB -