oj.uz

Submission #1106001

# Submission time Handle Problem Language Result Execution time Memory
1106001 2024-10-28T16:59:03 Z farica Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 835 ms 49296 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX_N = 2e5;
const int MOD = 998244353;

struct Node {
    int borders[2], dp[2][2];

    Node() {
        borders[0] = borders[1] = 0;
        dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = 0;
    }
};

Node segm[4*MAX_N];
int a[MAX_N];

void calc(int pos, int l, int r) {
    Node ret;
    ret.borders[0] = segm[2*pos+1].borders[0];
    ret.borders[1] = segm[2*pos+2].borders[1];
    for(int l=0; l<2; ++l) for(int m=0; m<2; ++m) for(int o=0; o<2; ++o) for(int r=0; r<2; ++r) {
        if(o && m) {
            if((segm[2*pos+1].borders[1] < 0) == (segm[2*pos+2].borders[0] < 0)) ret.dp[l][r] = max(ret.dp[l][r], segm[2*pos+1].dp[l][m] + segm[2*pos+2].dp[o][r]);
        } else ret.dp[l][r] = max(ret.dp[l][r], segm[2*pos+1].dp[l][m] + segm[2*pos+2].dp[o][r]);
    }
    segm[pos] = ret;
}

void update(int pos, int l, int r, int x, int val) {
    if(l==r) {
        segm[pos].borders[0] += val;
        segm[pos].borders[1] += val;
        segm[pos].dp[1][1] = abs(segm[pos].borders[0]);
        return;
    }
    int m = (l+r)/2;
    if(x <= m) update(2*pos+1, l, m, x, val);
    else update(2*pos+2, m+1, r, x, val);
    calc(pos, l, r);
}

void build(int pos, int l, int r) {
    if(l==r) {
        segm[pos].borders[0] += a[l+1] - a[l];
        segm[pos].borders[1] += a[l+1] - a[l];
        segm[pos].dp[1][1] = abs(segm[pos].borders[0]);
        return;
    }
    int m = (l+r)/2;
    build(2*pos+1, l, m);
    build(2*pos+2, m+1, r);
    calc(pos, l, r);
}

void solve() {
    for(int i=0; i<4*MAX_N; ++i) {
        segm[i].borders[0] = segm[i].borders[1] = 0;
        for(int j=0; j<2; ++j) for(int k=0; k<2; ++k) segm[i].dp[j][k] = 0;
    }
    int n, q;
    cin >> n >> q;
    for(int i=0; i<n; ++i) {
        cin >> a[i];
    }
    build(1, 0, n-2);
    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;
        --l, --r;
        if(l) update(1, 0, n-2, l-1, x);
        if(r != n-1) update(1, 0, n-2, r, -x);
        cout << segm[1].dp[1][1] << endl;
    }
}

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

    int t = 1;
    while(t--) solve();

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39248 KB Output is correct
2 Correct 9 ms 39248 KB Output is correct
3 Correct 11 ms 39248 KB Output is correct
4 Correct 9 ms 39248 KB Output is correct
5 Correct 9 ms 39248 KB Output is correct
6 Correct 9 ms 39248 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39248 KB Output is correct
2 Correct 9 ms 39248 KB Output is correct
3 Correct 11 ms 39248 KB Output is correct
4 Correct 9 ms 39248 KB Output is correct
5 Correct 9 ms 39248 KB Output is correct
6 Correct 9 ms 39248 KB Output is correct
7 Correct 16 ms 39504 KB Output is correct
8 Correct 17 ms 39504 KB Output is correct
9 Correct 19 ms 39504 KB Output is correct
10 Correct 16 ms 39504 KB Output is correct
11 Correct 17 ms 39504 KB Output is correct
12 Correct 17 ms 39524 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39248 KB Output is correct
2 Correct 9 ms 39248 KB Output is correct
3 Correct 11 ms 39248 KB Output is correct
4 Correct 9 ms 39248 KB Output is correct
5 Correct 9 ms 39248 KB Output is correct
6 Correct 9 ms 39248 KB Output is correct
7 Correct 16 ms 39504 KB Output is correct
8 Correct 17 ms 39504 KB Output is correct
9 Correct 19 ms 39504 KB Output is correct
10 Correct 16 ms 39504 KB Output is correct
11 Correct 17 ms 39504 KB Output is correct
12 Correct 17 ms 39524 KB Output is correct
13 Correct 801 ms 48636 KB Output is correct
14 Correct 835 ms 48712 KB Output is correct
15 Correct 715 ms 48576 KB Output is correct
16 Correct 802 ms 48456 KB Output is correct
17 Correct 769 ms 48484 KB Output is correct
18 Correct 677 ms 49296 KB Output is correct