oj.uz

Submission #566247

# Submission time Handle Problem Language Result Execution time Memory
566247 2022-05-22T07:53:14 Z Tam_theguide Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 720 ms 29604 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18;
int n , q; ll a[200005], d[200005];
struct node{
    ll a[2][2];
    void init(){
        for (int i = 0; i <= 1; i++){
            for (int j = 0; j <= 1; j++){
                a[i][j] = -INF;
            }
        }
    }

};
node seg[800005];
void push(int root, int tl, int tr){
    int tm = (tl + tr) / 2; node c1 = seg[2 * root], c2 = seg[2 * root + 1];
    ll tmp[2][2];
    for (int i = 0; i <= 1; i++) for (int j = 0; j <= 1; j ++) tmp[i][j] = -1e18;
    for (int i = 0; i <= 1; i++){
        for (int j = 0; j <= 1; j++){
            for (int t = 0; t <= 1; t++){
                for (int k = 0; k <= 1; k++){
                    if (c1.a[i][j] != -INF && c2.a[t][k] != -INF){

                        if (j == 1 && t == 1 && d[tm] * d[tm + 1] < 0) continue;

                        tmp[i][k] = max(tmp[i][k], c1.a[i][j] + c2.a[t][k]);
                    }
                }
            }
        }
    }
    for (int i = 0; i <= 1; i++) for (int j = 0; j <= 1;j ++) seg[root].a[i][j] = tmp[i][j];
}
void buildtree(int root, int tl, int tr){
    if (tl == tr){
        seg[root].init();
        seg[root].a[1][1] = abs(d[tl]);
        seg[root].a[0][0] = 0;
        return;
    }
    int tm = (tl + tr) / 2;
    buildtree(2 * root, tl, tm);
    buildtree(2 * root + 1, tm + 1, tr);
    push(root, tl, tr);
}
void update(int root, int tl, int tr, int pos){
    if (tl == tr){
        seg[root].init();
        seg[root].a[1][1] = abs(d[tl]);
        seg[root].a[0][0] = 0;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) update(2 * root, tl, tm, pos);
    else update(2 * root + 1, tm + 1, tr, pos);
    push(root, tl, tr);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q; for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i < n;i++) d[i] = a[i] - a[i + 1];
    //for (int i = 0; i <= 4 * n; i++) seg[i].init();
    //cout << seg[1].a[0][1] + INF;
    buildtree(1, 1, n - 1);
    while (q--){
        int l, r; ll x; cin >> l >> r >> x;
        d[l - 1] -= x; d[r] += x;
        update(1, 1, n - 1, l - 1); update(1, 1, n - 1, r);
        cout << max({seg[1].a[0][0], seg[1].a[0][1], seg[1].a[1][1], seg[1].a[1][0]}) << '\n';
    }
}

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 336 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 340 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 336 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 340 KB Output is correct
7 Correct 7 ms 724 KB Output is correct
8 Correct 6 ms 736 KB Output is correct
9 Correct 7 ms 764 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 7 ms 736 KB Output is correct
12 Correct 9 ms 692 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 336 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 340 KB Output is correct
7 Correct 7 ms 724 KB Output is correct
8 Correct 6 ms 736 KB Output is correct
9 Correct 7 ms 764 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 7 ms 736 KB Output is correct
12 Correct 9 ms 692 KB Output is correct
13 Correct 720 ms 29104 KB Output is correct
14 Correct 709 ms 28996 KB Output is correct
15 Correct 675 ms 28988 KB Output is correct
16 Correct 684 ms 28996 KB Output is correct
17 Correct 671 ms 28816 KB Output is correct
18 Correct 639 ms 29604 KB Output is correct