oj.uz

Submission #386341

# Submission time Handle Problem Language Result Execution time Memory
386341 2021-04-06T12:11:33 Z phathnv Sjeckanje (COCI21_sjeckanje) C++11
110 / 110
 1230 ms 54764 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e5 + 1;
const ll INF = 1e18;

int n, q, a[N];

int getSign(ll x){
    if (x < 0)
        return -1;
    else if (x == 0)
        return 0;
    else
        return 1;
}

struct Node{
    ll val, dp[2][2], leftVal, rightVal;
    Node(){
        val = leftVal = rightVal = 0;
        dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = 0;
    }
    void update(ll delta){
        val += delta;
        dp[0][0] = 0;
        dp[1][1] = abs(val);
        dp[0][1] = dp[1][0] = -INF;
        leftVal = rightVal = val;
    }
    Node operator + (const Node &oth){
        Node res;
        res.leftVal = leftVal;
        res.rightVal = oth.rightVal;
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                res.dp[i][j] = -INF;
        for(int a = 0; a < 2; a++)
            for(int b = 0; b < 2; b++)
                for(int c = 0; c < 2; c++)
                    for(int d = 0; d < 2; d++){
                        ll val = dp[a][b] + oth.dp[c][d];
                        if (b && c && getSign(rightVal) * getSign(oth.leftVal) == -1)
                            val -= min(abs(rightVal), abs(oth.leftVal));
                        res.dp[a][d] = max(res.dp[a][d], val);
                    }
        return res;
    }
};

struct segmentTree{
    Node d[N * 4];
    void update(int id, int l, int r, int pos, int val){
        if (pos < l || r < pos)
            return;
        if (l == r){
            d[id].update(val);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, pos, val);
        update(id << 1 | 1, mid + 1, r, pos, val);
        d[id] = d[id << 1] + d[id << 1 | 1];
    }
    ll solve(){
        return max(max(d[1].dp[0][0], d[1].dp[0][1]), max(d[1].dp[1][0], d[1].dp[1][1]));
    }
} ST;

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

    cin >> n >> q;

    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i < n; i++)
        ST.update(1, 1, n - 1, i, a[i + 1] - a[i]);

    while (q--){
        int l, r, x;
        cin >> l >> r >> x;
        if (l > 1)
            ST.update(1, 1, n - 1, l - 1, x);
        if (r < n)
            ST.update(1, 1, n - 1, r, -x);
        cout << ST.solve() << '\n';
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 44140 KB Output is correct
2 Correct 28 ms 44152 KB Output is correct
3 Correct 26 ms 44140 KB Output is correct
4 Correct 27 ms 44140 KB Output is correct
5 Correct 27 ms 44140 KB Output is correct
6 Correct 27 ms 44140 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 44140 KB Output is correct
2 Correct 28 ms 44152 KB Output is correct
3 Correct 26 ms 44140 KB Output is correct
4 Correct 27 ms 44140 KB Output is correct
5 Correct 27 ms 44140 KB Output is correct
6 Correct 27 ms 44140 KB Output is correct
7 Correct 37 ms 44268 KB Output is correct
8 Correct 38 ms 44268 KB Output is correct
9 Correct 36 ms 44268 KB Output is correct
10 Correct 36 ms 44268 KB Output is correct
11 Correct 36 ms 44268 KB Output is correct
12 Correct 37 ms 44268 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 44140 KB Output is correct
2 Correct 28 ms 44152 KB Output is correct
3 Correct 26 ms 44140 KB Output is correct
4 Correct 27 ms 44140 KB Output is correct
5 Correct 27 ms 44140 KB Output is correct
6 Correct 27 ms 44140 KB Output is correct
7 Correct 37 ms 44268 KB Output is correct
8 Correct 38 ms 44268 KB Output is correct
9 Correct 36 ms 44268 KB Output is correct
10 Correct 36 ms 44268 KB Output is correct
11 Correct 36 ms 44268 KB Output is correct
12 Correct 37 ms 44268 KB Output is correct
13 Correct 1207 ms 48236 KB Output is correct
14 Correct 1204 ms 54100 KB Output is correct
15 Correct 1202 ms 54392 KB Output is correct
16 Correct 1179 ms 54100 KB Output is correct
17 Correct 1165 ms 54124 KB Output is correct
18 Correct 1230 ms 54764 KB Output is correct