oj.uz

Submission #870136

# Submission time Handle Problem Language Result Execution time Memory
870136 2023-11-07T03:03:53 Z LTTrungCHL Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 378 ms 32780 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int OFF = 1 << 18;
const ll INF = 4.5e18;

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

void maxeq(ll& x, ll y) {
    x = max(x, y);
}

ll t[2 * OFF][2][2], d[OFF];
int l[2 * OFF], r[2 * OFF], m[2 * OFF];

void update(int i, ll x) {
    d[i] += x;

    i += OFF;
    t[i][0][0] = 0;
    t[i][1][1] = abs(d[m[i]]);
    t[i][0][1] = t[i][1][0] = -INF;

    for (i /= 2; i > 0; i /= 2) {
        for (int lb : {0, 1}) for (int rb : {0, 1}) {
            ll& T = t[i][lb][rb];
            T = -INF;
            maxeq(T, t[2 * i][lb][0] + t[2 * i + 1][0][rb]);
            maxeq(T, t[2 * i][lb][1] + t[2 * i + 1][0][rb]);
            maxeq(T, t[2 * i][lb][0] + t[2 * i + 1][1][rb]);
            if (sgn(d[m[i] - 1]) * sgn(d[m[i]]) != -1)
                maxeq(T, t[2 * i][lb][1] + t[2 * i + 1][1][rb]);
        }
    }
}

ll query() {
    return max(max(t[1][0][0], t[1][0][1]),
               max(t[1][1][0], t[1][1][1]));
}

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

    l[1] = 0, r[1] = OFF;
    for (int i = 1; i < 2 * OFF; i++) {
        m[i] = (l[i] + r[i]) / 2;
        if (i < OFF) {
            l[2 * i + 0] = l[i];
            r[2 * i + 0] = l[2 * i + 1] = m[i];
            r[2 * i + 1] = r[i];
        }
    }

    int n, q;
    cin >> n >> q;
    ll x;
    for (int i = 0; i < n; i++) {
        ll y;
        cin >> y;
        if (i > 0) update(i - 1, x - y);
        x = y;
    }

    while (q--) {
        int lq, rq;
        ll w;
        cin >> lq >> rq >> w;

        if (lq > 1) update(lq - 2, -w);
        if (rq < n) update(rq - 1, +w);

        cout << query() << '\n';
    }

    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 7 ms 14940 KB Output is correct
8 Correct 7 ms 14940 KB Output is correct
9 Correct 8 ms 14968 KB Output is correct
10 Correct 7 ms 14940 KB Output is correct
11 Correct 7 ms 14940 KB Output is correct
12 Correct 6 ms 14940 KB Output is correct
13 Correct 364 ms 32332 KB Output is correct
14 Correct 369 ms 32332 KB Output is correct
15 Correct 369 ms 32312 KB Output is correct
16 Correct 372 ms 32124 KB Output is correct
17 Correct 378 ms 32088 KB Output is correct
18 Correct 316 ms 32780 KB Output is correct