oj.uz

Submission #993543

# Submission time Handle Problem Language Result Execution time Memory
993543 2024-06-06T02:46:44 Z vjudge1 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 351 ms 38560 KB 
/*
    Author: tminh_hk20
    Task:
*/

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define getbit(x,y) ((x) & (1ll<<(y)));
#define turnon(x,y) ((x) | (1ll<<(y)));
#define turnoff(x,y) ((x) ^ (1ll<<(y)));

using namespace std;
const int N =2e5;
const int MOD = 998244353;

ll n, q, a[N+10], b[N+10];

struct node{
    ll f[2][2], lef, rig;
}st[4*N+10];

node combine(node a, node b){
    node res;
    res.lef = a.lef;
    res.rig = b.rig;

    res.f[0][0] = max({0ll,a.f[0][0]+b.f[1][0],a.f[0][1]+b.f[0][0], a.f[0][0]+b.f[0][0]});
    res.f[1][0] = max({0ll,a.f[1][0]+b.f[1][0], a.f[1][1]+b.f[0][0], a.f[1][0]+b.f[0][0]});
    res.f[0][1] = max({0ll,a.f[0][1]+b.f[0][1], a.f[0][0]+b.f[1][1],a.f[0][0]+b.f[0][1]});
    res.f[1][1] = max({0ll,a.f[1][0]+b.f[1][1], a.f[1][1]+b.f[0][1],a.f[1][0]+b.f[0][1]});
    if (a.rig*b.lef>=0){
        res.f[0][0] = max(res.f[0][0], a.f[0][1]+b.f[1][0]);
        res.f[1][0] = max(res.f[1][0], a.f[1][1]+b.f[1][0]);
        res.f[0][1] = max(res.f[0][1], a.f[0][1]+b.f[1][1]);
        res.f[1][1] = max(res.f[1][1], a.f[1][1]+b.f[1][1]);
    }

    return res;
}

void build(int id,int l, int r){
    if (l==r){
        st[id].f[1][1] = abs(b[l]);
        st[id].f[0][0] = 0;
        st[id].f[1][0] = 0;
        st[id].f[0][1] = 0;
        st[id].lef = st[id].rig = b[l];
        return;
    }

    int m = (l+r)/2;
    build(2*id,l,m);
    build(2*id+1,m+1,r);
    st[id] = combine(st[2*id],st[2*id+1]);
//    cout <<">"<<id<<" "<<l<<" "<<r<<" "<<" "<<st[id].lef<<" "<<st[id].rig<<" <> "<<st[id].f[1][0]<<" "<<st[id].f[0][1]<<" "<<st[id].f[0][0]<<" "<<st[id].f[1][1]<<endl;
}

void up(int id, int l, int r, int i, int val){
    if (i> r || i<l) return;
    if (l==r && i==l){
        st[id].f[1][1] = abs(val);
        st[id].f[0][0] = 0;
        st[id].f[1][0] = 0;
        st[id].f[0][1] = 0;
        st[id].lef = st[id].rig = val;
        return;
    }

    int m = (l+r)/2;
    up(2*id,l,m,i,val);
    up(2*id+1,m+1,r,i,val);
    st[id] = combine(st[2*id],st[2*id+1]);
}

void solve(){
    cin>> n>> q;
    for (int i=1;i<=n;i++) cin>> a[i];

    for (int i=1;i<n;i++) b[i] = a[i+1]- a[i];
    n--;
    build(1,1,n);
    while(q--){
        int l, r, x; cin>>l>>r>>x;
        b[l-1] +=x; b[r]-=x;
        up(1,1,n,l-1,b[l-1]);
        up(1,1,n,r,b[r]);

        node res = st[1];
        cout << max({res.f[0][0],res.f[1][0],res.f[0][1],res.f[1][1]})<<endl;
//        for (int i=1;i<=n;i++) cout << b[i]<<" "; cout<<endl;
    }



}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

//    freopen("bai.inp","r",stdin);
//    freopen("bai.out","w",stdout);

    int T = 1;
    while(T--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2520 KB Output is correct
2 Correct 1 ms 2480 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2520 KB Output is correct
2 Correct 1 ms 2480 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 4 ms 4700 KB Output is correct
8 Correct 4 ms 4700 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 4 ms 4700 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2520 KB Output is correct
2 Correct 1 ms 2480 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 4 ms 4700 KB Output is correct
8 Correct 4 ms 4700 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 4 ms 4700 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 304 ms 37836 KB Output is correct
14 Correct 292 ms 37968 KB Output is correct
15 Correct 339 ms 37964 KB Output is correct
16 Correct 351 ms 37892 KB Output is correct
17 Correct 274 ms 37796 KB Output is correct
18 Correct 256 ms 38560 KB Output is correct