oj.uz

Submission #839025

# Submission time Handle Problem Language Result Execution time Memory
839025 2023-08-28T13:40:23 Z 8pete8 Progression (NOI20_progression) C++14
57 / 100
 922 ms 47892 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=1e9;
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;
    node le=query(pos*2,l,mid,ql,qr);
    node ri=query(pos*2+1,mid+1,r,ql,qr);
    return comb(le,ri);
}
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 116 ms 31324 KB Output is correct
2 Correct 64 ms 1084 KB Output is correct
3 Correct 63 ms 1100 KB Output is correct
4 Correct 62 ms 1044 KB Output is correct
5 Correct 63 ms 1176 KB Output is correct
6 Correct 67 ms 1232 KB Output is correct
7 Correct 64 ms 1112 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 116 ms 38840 KB Output is correct
12 Correct 117 ms 38772 KB Output is correct
13 Correct 122 ms 39016 KB Output is correct
14 Correct 118 ms 39112 KB Output is correct
15 Correct 116 ms 39028 KB Output is correct
16 Correct 156 ms 38732 KB Output is correct
17 Correct 122 ms 38796 KB Output is correct
18 Correct 133 ms 38756 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 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 248 ms 39916 KB Output is correct
2 Correct 76 ms 1408 KB Output is correct
3 Correct 75 ms 1432 KB Output is correct
4 Correct 65 ms 1444 KB Output is correct
5 Correct 71 ms 1484 KB Output is correct
6 Correct 70 ms 1484 KB Output is correct
7 Correct 70 ms 1412 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 286 ms 44068 KB Output is correct
12 Correct 283 ms 45560 KB Output is correct
13 Correct 302 ms 44120 KB Output is correct
14 Correct 278 ms 44124 KB Output is correct
15 Correct 268 ms 45516 KB Output is correct
16 Correct 273 ms 46028 KB Output is correct
17 Correct 280 ms 46016 KB Output is correct
18 Correct 276 ms 46072 KB Output is correct
19 Correct 247 ms 45388 KB Output is correct
20 Correct 251 ms 45412 KB Output is correct
21 Correct 229 ms 45476 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 39148 KB Output is correct
2 Incorrect 130 ms 1152 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 248 ms 39916 KB Output is correct
2 Correct 76 ms 1408 KB Output is correct
3 Correct 75 ms 1432 KB Output is correct
4 Correct 65 ms 1444 KB Output is correct
5 Correct 71 ms 1484 KB Output is correct
6 Correct 70 ms 1484 KB Output is correct
7 Correct 70 ms 1412 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 286 ms 44068 KB Output is correct
12 Correct 283 ms 45560 KB Output is correct
13 Correct 302 ms 44120 KB Output is correct
14 Correct 278 ms 44124 KB Output is correct
15 Correct 268 ms 45516 KB Output is correct
16 Correct 273 ms 46028 KB Output is correct
17 Correct 280 ms 46016 KB Output is correct
18 Correct 276 ms 46072 KB Output is correct
19 Correct 247 ms 45388 KB Output is correct
20 Correct 251 ms 45412 KB Output is correct
21 Correct 229 ms 45476 KB Output is correct
22 Correct 714 ms 47700 KB Output is correct
23 Correct 133 ms 3512 KB Output is correct
24 Correct 143 ms 3568 KB Output is correct
25 Correct 136 ms 3544 KB Output is correct
26 Correct 136 ms 3580 KB Output is correct
27 Correct 143 ms 3564 KB Output is correct
28 Correct 136 ms 3516 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 684 ms 44980 KB Output is correct
33 Correct 642 ms 47724 KB Output is correct
34 Correct 664 ms 44904 KB Output is correct
35 Correct 922 ms 45060 KB Output is correct
36 Correct 570 ms 44808 KB Output is correct
37 Correct 565 ms 44724 KB Output is correct
38 Correct 563 ms 44748 KB Output is correct
39 Correct 678 ms 47864 KB Output is correct
40 Correct 703 ms 47876 KB Output is correct
41 Correct 729 ms 47820 KB Output is correct
42 Correct 682 ms 47892 KB Output is correct
43 Correct 654 ms 47852 KB Output is correct
44 Correct 658 ms 47636 KB Output is correct
45 Correct 671 ms 47744 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 31324 KB Output is correct
2 Correct 64 ms 1084 KB Output is correct
3 Correct 63 ms 1100 KB Output is correct
4 Correct 62 ms 1044 KB Output is correct
5 Correct 63 ms 1176 KB Output is correct
6 Correct 67 ms 1232 KB Output is correct
7 Correct 64 ms 1112 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 116 ms 38840 KB Output is correct
12 Correct 117 ms 38772 KB Output is correct
13 Correct 122 ms 39016 KB Output is correct
14 Correct 118 ms 39112 KB Output is correct
15 Correct 116 ms 39028 KB Output is correct
16 Correct 156 ms 38732 KB Output is correct
17 Correct 122 ms 38796 KB Output is correct
18 Correct 133 ms 38756 KB Output is correct
19 Incorrect 3 ms 340 KB Output isn't correct
20 Halted 0 ms 0 KB -