oj.uz

Submission #657823

# Submission time Handle Problem Language Result Execution time Memory
657823 2022-11-11T11:49:47 Z HungAnhGoldIBO2020 Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 459 ms 28016 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+2;
int ar[N],it[4*N][2][2];
bool samesign(int a,int b){
    if(a==0||b==0){
        return true;
    }
    if(a>0&&b>0){
        return true;
    }
    if(a<0&&b<0){
        return true;
    }
    return false;
}
void pull(int idx,int l,int r){
    int mid=(l+r)>>1;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            it[idx][i][j]=max(it[2*idx][i][0]+it[2*idx+1][1][j],max(it[2*idx][i][0]+it[2*idx+1][0][j],it[2*idx][i][1]+it[2*idx+1][0][j]));
            if(samesign(ar[mid],ar[mid+1])){
                it[idx][i][j]=max(it[idx][i][j],it[2*idx][i][1]+it[2*idx+1][1][j]);
            }
        }
    }
}
void init(int idx,int l,int r){
    if(l==r){
        if(ar[l]<0){
            it[idx][1][1]=-ar[l];
        }
        else{
            it[idx][1][1]=ar[l];
        }
        return;
    }
    int mid=(l+r)>>1;
    init(2*idx,l,mid);
    init(2*idx+1,mid+1,r);
    pull(idx,l,r);
}
void upd(int idx,int l,int r,int pos){
    if(pos>r||pos<l){
        return;
    }
    if(l==r){
        if(ar[l]<0){
            it[idx][1][1]=-ar[l];
        }
        else{
            it[idx][1][1]=ar[l];
        }
        return;
    }
    int mid=(l+r)>>1;
    upd(2*idx,l,mid,pos);
    upd(2*idx+1 ,mid+1,r,pos);
    pull(idx,l,r);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,q,i,j,k,l;
    cin>>n>>q;
    if(n==1){
        for(i=1;i<=q;i++){
            cout<<0<<'\n';
        }
        return 0;
    }
    for(i=1;i<=n;i++){
        cin>>j;
        if(i>1){
            ar[i-1]=j-k;
        }
        k=j;
    }
    n--;
    init(1,1,n);
    for(i=1;i<=q;i++){
        //cout<<i<<" KEK"<<endl;
        cin>>j>>k>>l;
        if(j>1){
            ar[j-1]+=l;
            upd(1,1,n,j-1);
        }
        if(k<=n){
            ar[k]-=l;
            upd(1,1,n,k);
        }
        /*
        for(j=1;j<=n;j++){
            cout<<ar[j]<<' ';
        }
        cout<<'\n';
        */
        cout<<max(max(it[1][0][0],it[1][1][1]),max(it[1][0][1],it[1][1][0]))<<'\n';
    }
}
/*
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 4 ms 740 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 4 ms 752 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 4 ms 740 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 4 ms 752 KB Output is correct
13 Correct 459 ms 27404 KB Output is correct
14 Correct 412 ms 27372 KB Output is correct
15 Correct 452 ms 27392 KB Output is correct
16 Correct 386 ms 27328 KB Output is correct
17 Correct 395 ms 27224 KB Output is correct
18 Correct 413 ms 28016 KB Output is correct