oj.uz

Submission #366877

# Submission time Handle Problem Language Result Execution time Memory
366877 2021-02-15T15:14:39 Z valerikk Two Antennas (JOI19_antennas) C++17
22 / 100
 566 ms 33964 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 7;
const int INF = 1e9 + 1010;

int n, q;
int h[N], a[N], b[N];
int L[N], R[N];
int ans[N];
int c[N];
int t[4 * N]; // max d[i]
int min_h[4 * N]; 
int max_c[4 * N];
vector<pair<int, int>> events[N];
vector<int> here[N];

void upd(int i, int val) {
    min_h[i] = min(min_h[i], val);
    t[i] = max(t[i], max_c[i] - min_h[i]);
}

void push(int i) {
    upd(2 * i, min_h[i]);
    upd(2 * i + 1, min_h[i]);
    min_h[i] = INF;
}

void pull(int i) {
    max_c[i] = max(max_c[2 * i], max_c[2 * i + 1]);
    t[i] = max({t[i], max_c[i] - min_h[i], t[2 * i], t[2 * i + 1]});
}

void upd_seg(int i, int l, int r, int ql, int qr, int val) {
    if (l >= qr || r <= ql)
        return;
    if (l >= ql && r <= qr) {
        upd(i, val);
        return;
    }

    push(i);
    int m = (l + r) / 2;
    upd_seg(2 * i, l, m, ql, qr, val);
    upd_seg(2 * i + 1, m, r, ql, qr, val);
    pull(i);
}

void upd_c(int i, int l, int r, int pos, int new_c) {
    if (r - l == 1) {
        min_h[i] = INF;
        c[pos] = max_c[i] = new_c;
        t[i] = -1;
    } else {
        push(i);
        int m = (l + r) / 2;
        if (pos < m)
            upd_c(2 * i, l, m, pos, new_c);
        else 
            upd_c(2 * i + 1, m, r, pos, new_c);
        pull(i);
    }
}

int get_max(int i, int l, int r, int ql, int qr) {
    if (l >= qr || r <= ql)
        return -1;
    if (l >= ql && r <= qr)
        return t[i];
    push(i);
    int m = (l + r) / 2;
    return max(get_max(2 * i, l, m, ql, qr), get_max(2 * i + 1, m, r, ql, qr));
}

void build(int i, int l, int r) {
    min_h[i] = INF;
    if (r - l == 1) {
        c[l] = max_c[i] = -1;
        t[i] = -1;
    } else {
        int m = (l + r) / 2;
        build(2 * i, l, m);
        build(2 * i + 1, m, r);
        t[i] = -1;
        pull(i);
    }
}

void solve() {
    for (int i = 0; i <= n; i++) {
        events[i].clear();
        here[i].clear();
    }
    for (int i = 0; i < n; i++) {
        int l = i + a[i], r = min(n, i + b[i] + 1);
        if (l < r) {
            events[l].emplace_back(i, h[i]);
            events[r].emplace_back(i, -1);
        }
    }
    
    for (int i = 0; i < q; i++) 
        here[R[i]].push_back(i);
    
    build(1, 0, n);
    for (int i = 0; i <= n; i++) {
        for (int qid : here[i]) 
            ans[qid] = max(ans[qid], get_max(1, 0, n, L[qid], R[qid]));

        for (auto [pos, new_c] : events[i]) 
            upd_c(1, 0, n, pos, new_c);
        if (i != n) {
            int l = max(0, i - b[i]), r = i - a[i] + 1;
            if (l < r)
                upd_seg(1, 0, n, l, r, h[i]);
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> h[i] >> a[i] >> b[i];
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> L[i] >> R[i];
        L[i]--;
        ans[i] = -1;
    }
    
    for (int _ = 0; _ < 2; _++) {
        solve();
        reverse(h, h + n);
        reverse(a, a + n);
        reverse(b, b + n);
        for (int i = 0; i < q; i++) {
            R[i]--;
            L[i] = n - 1 - L[i];
            R[i] = n - 1 - R[i];
            swap(L[i], R[i]);
            R[i]++;
        }
    }

    for (int i = 0; i < q; i++) 
        cout << ans[i] << "\n";
    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 32100 KB Output is correct
2 Correct 566 ms 33464 KB Output is correct
3 Correct 341 ms 29416 KB Output is correct
4 Correct 520 ms 33252 KB Output is correct
5 Correct 209 ms 23272 KB Output is correct
6 Correct 511 ms 33380 KB Output is correct
7 Correct 433 ms 31588 KB Output is correct
8 Correct 539 ms 33380 KB Output is correct
9 Correct 65 ms 17260 KB Output is correct
10 Correct 555 ms 33380 KB Output is correct
11 Correct 282 ms 25448 KB Output is correct
12 Correct 513 ms 33252 KB Output is correct
13 Correct 411 ms 33376 KB Output is correct
14 Correct 371 ms 33328 KB Output is correct
15 Correct 350 ms 32056 KB Output is correct
16 Correct 334 ms 32428 KB Output is correct
17 Correct 415 ms 33964 KB Output is correct
18 Correct 377 ms 32876 KB Output is correct
19 Correct 383 ms 32988 KB Output is correct
20 Correct 370 ms 33116 KB Output is correct
21 Correct 354 ms 33108 KB Output is correct
22 Correct 370 ms 33028 KB Output is correct
23 Correct 371 ms 33380 KB Output is correct
24 Correct 318 ms 31780 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14444 KB Output isn't correct
2 Halted 0 ms 0 KB -