oj.uz

답안 #378462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
378462 2021-03-16T21:39:48 Z cuom1999 Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1066 ms 48664 KB 
#include <bits/stdc++.h>
using namespace std;

int a[200005];

int sgn(long long x) {
    if (x > 0) return 1;
    if (x < 0) return -1;
    return 0;
}

struct IT {
    struct Node {
        long long value[2][2] = {0};
        long long lValue, rValue;
    };
    vector<Node> st;
    IT(int n) {
        st.resize(4 * n);
    }

    Node combine(Node a, Node b) {
        Node res;
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 1; k++) {
                    for (int k1 = 0; k1 <= 1; k1++) {
                        int sign = sgn(a.rValue) * sgn(b.lValue);
                        if (k == 1 && k1 == 1 && sign == -1) continue; 
                        res.value[i][j] = max(res.value[i][j], a.value[i][k] + b.value[k1][j]);
                    }
                }
            }
        }
        res.lValue = a.lValue;
        res.rValue = b.rValue;
        return res;
    }

    void build(int id, int l, int r) {
        if (l == r) {
            st[id].value[1][1] = abs(a[l + 1] - a[l]);
            st[id].lValue = st[id].rValue = a[l + 1] - a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        st[id] = combine(st[id * 2], st[id * 2 + 1]);
        // cout << id << " " << st[id].value[1][0] << endl;
    }

    void update(int id, int l, int r, int u, long long v) {
        if (l == r) {
            long long val = st[id].lValue + v;
            st[id].lValue = st[id].rValue = val;
            st[id].value[1][1] = abs(val);
            // cout << l << " " << val << endl;
            return;
        }
        int mid = (l + r) / 2;
        if (u <= mid) update(id * 2, l, mid, u, v);
        else update(id * 2 + 1, mid + 1, r, u, v);
        st[id] = combine(st[id * 2], st[id * 2 + 1]);
    }
    long long getValue(int id) {
        long long res = 0;
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j <= 1; j++) {
                res = max(res, st[id].value[i][j]);
            }
        }
        return res;
    } 
};

int main() {
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(NULL);

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

    IT seg(n);
    seg.build(1, 1, n - 1);

    // cout << seg.getValue(1) << endl;
    // return 0;
    for (int z = 1; z <= q; z++) {
        int l, r, x;
        cin >> l >> r >> x;
        l--;
        if (l > 0) seg.update(1, 1, n - 1, l, x);
        if (r < n) seg.update(1, 1, n - 1, r, -x);
        cout << seg.getValue(1) << "\n";
    }


    return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 10 ms 1004 KB Output is correct
8 Correct 10 ms 1004 KB Output is correct
9 Correct 10 ms 1004 KB Output is correct
10 Correct 10 ms 1004 KB Output is correct
11 Correct 10 ms 1004 KB Output is correct
12 Correct 10 ms 1260 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 10 ms 1004 KB Output is correct
8 Correct 10 ms 1004 KB Output is correct
9 Correct 10 ms 1004 KB Output is correct
10 Correct 10 ms 1004 KB Output is correct
11 Correct 10 ms 1004 KB Output is correct
12 Correct 10 ms 1260 KB Output is correct
13 Correct 1056 ms 48060 KB Output is correct
14 Correct 1066 ms 47980 KB Output is correct
15 Correct 1052 ms 48112 KB Output is correct
16 Correct 1018 ms 47852 KB Output is correct
17 Correct 1028 ms 47924 KB Output is correct
18 Correct 1051 ms 48664 KB Output is correct