oj.uz

Submission #839270

# Submission time Handle Problem Language Result Execution time Memory
839270 2023-08-29T13:26:20 Z 8pete8 Progression (NOI20_progression) C++17
68 / 100
 786 ms 78956 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];
bool yes[4*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(yes[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(yes[pos]){
        app(pos);
        if(l!=r){
            add[pos*2]=0;
            add[pos*2+1]=0;
            yes[pos*2]=true;
            yes[pos*2+1]=true;
            change[pos*2]=change[pos];
            change[pos*2+1]=change[pos];
        }
    }
    add[pos]=0;
    yes[pos]=false;
    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;
        yes[pos]=true;
        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(ql<=mid&&mid<qr)return comb(query(pos*2,l,mid,ql,qr),query(pos*2+1,mid+1,r,ql,qr));
    if(ql<=mid)return query(pos*2,l,mid,ql,qr);
    return 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];
    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;
            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;
            sumr=query(1,0,n-1,0,r).sum+val;
            diff=sumr-(x+(r-l)*c);
            update2(1,0,n-1,r,r,diff);
            if(l){
                if(l>1)suml=query(1,0,n-1,0,l-2).sum+val;
                else suml=val;
                diff=x-suml;
                update2(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 358 ms 60828 KB Output is correct
2 Correct 120 ms 740 KB Output is correct
3 Correct 110 ms 588 KB Output is correct
4 Correct 108 ms 584 KB Output is correct
5 Correct 113 ms 704 KB Output is correct
6 Correct 114 ms 716 KB Output is correct
7 Correct 112 ms 716 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 336 ms 60996 KB Output is correct
12 Correct 357 ms 60724 KB Output is correct
13 Correct 338 ms 61080 KB Output is correct
14 Correct 333 ms 61080 KB Output is correct
15 Correct 334 ms 61052 KB Output is correct
16 Correct 339 ms 60756 KB Output is correct
17 Correct 336 ms 60832 KB Output is correct
18 Correct 354 ms 60784 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 246 ms 78540 KB Output is correct
2 Correct 66 ms 844 KB Output is correct
3 Correct 67 ms 836 KB Output is correct
4 Correct 55 ms 912 KB Output is correct
5 Correct 65 ms 972 KB Output is correct
6 Correct 67 ms 972 KB Output is correct
7 Correct 66 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 272 ms 78312 KB Output is correct
12 Correct 283 ms 78668 KB Output is correct
13 Correct 287 ms 78268 KB Output is correct
14 Correct 282 ms 78324 KB Output is correct
15 Correct 240 ms 78588 KB Output is correct
16 Correct 267 ms 78916 KB Output is correct
17 Correct 262 ms 78872 KB Output is correct
18 Correct 281 ms 78956 KB Output is correct
19 Correct 235 ms 78208 KB Output is correct
20 Correct 226 ms 78280 KB Output is correct
21 Correct 218 ms 78284 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 77772 KB Output is correct
2 Correct 136 ms 452 KB Output is correct
3 Correct 126 ms 736 KB Output is correct
4 Correct 121 ms 692 KB Output is correct
5 Correct 127 ms 672 KB Output is correct
6 Correct 126 ms 716 KB Output is correct
7 Correct 127 ms 784 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 607 ms 78036 KB Output is correct
12 Correct 596 ms 78032 KB Output is correct
13 Correct 606 ms 78124 KB Output is correct
14 Correct 599 ms 78144 KB Output is correct
15 Correct 558 ms 78024 KB Output is correct
16 Correct 618 ms 78200 KB Output is correct
17 Correct 608 ms 78160 KB Output is correct
18 Correct 621 ms 78128 KB Output is correct
19 Correct 639 ms 78036 KB Output is correct
20 Correct 570 ms 78052 KB Output is correct
21 Correct 626 ms 78148 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 78540 KB Output is correct
2 Correct 66 ms 844 KB Output is correct
3 Correct 67 ms 836 KB Output is correct
4 Correct 55 ms 912 KB Output is correct
5 Correct 65 ms 972 KB Output is correct
6 Correct 67 ms 972 KB Output is correct
7 Correct 66 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 272 ms 78312 KB Output is correct
12 Correct 283 ms 78668 KB Output is correct
13 Correct 287 ms 78268 KB Output is correct
14 Correct 282 ms 78324 KB Output is correct
15 Correct 240 ms 78588 KB Output is correct
16 Correct 267 ms 78916 KB Output is correct
17 Correct 262 ms 78872 KB Output is correct
18 Correct 281 ms 78956 KB Output is correct
19 Correct 235 ms 78208 KB Output is correct
20 Correct 226 ms 78280 KB Output is correct
21 Correct 218 ms 78284 KB Output is correct
22 Correct 721 ms 77940 KB Output is correct
23 Correct 157 ms 560 KB Output is correct
24 Correct 132 ms 608 KB Output is correct
25 Correct 132 ms 604 KB Output is correct
26 Correct 141 ms 592 KB Output is correct
27 Correct 136 ms 588 KB Output is correct
28 Correct 138 ms 552 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 783 ms 77888 KB Output is correct
33 Correct 707 ms 77832 KB Output is correct
34 Correct 747 ms 77968 KB Output is correct
35 Correct 768 ms 77996 KB Output is correct
36 Correct 581 ms 78280 KB Output is correct
37 Correct 586 ms 78196 KB Output is correct
38 Correct 565 ms 78216 KB Output is correct
39 Correct 723 ms 77900 KB Output is correct
40 Correct 760 ms 78044 KB Output is correct
41 Correct 786 ms 78004 KB Output is correct
42 Correct 748 ms 77984 KB Output is correct
43 Correct 734 ms 77916 KB Output is correct
44 Correct 700 ms 77960 KB Output is correct
45 Correct 746 ms 77924 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 60828 KB Output is correct
2 Correct 120 ms 740 KB Output is correct
3 Correct 110 ms 588 KB Output is correct
4 Correct 108 ms 584 KB Output is correct
5 Correct 113 ms 704 KB Output is correct
6 Correct 114 ms 716 KB Output is correct
7 Correct 112 ms 716 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 336 ms 60996 KB Output is correct
12 Correct 357 ms 60724 KB Output is correct
13 Correct 338 ms 61080 KB Output is correct
14 Correct 333 ms 61080 KB Output is correct
15 Correct 334 ms 61052 KB Output is correct
16 Correct 339 ms 60756 KB Output is correct
17 Correct 336 ms 60832 KB Output is correct
18 Correct 354 ms 60784 KB Output is correct
19 Incorrect 2 ms 468 KB Output isn't correct
20 Halted 0 ms 0 KB -