oj.uz

Submission #266414

# Submission time Handle Problem Language Result Execution time Memory
266414 2020-08-15T08:46:26 Z dolphingarlic Two Antennas (JOI19_antennas) C++14
22 / 100
 404 ms 41704 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, a[200001], b[200001];
ll h[200001], ans[200001];
vector<int> ins[400001], rem[400001];
ll segtree[800001];

void build(int node = 1, int l = 1, int r = n) {
    segtree[node] = INT_MIN;
    if (l != r) {
        int mid = (l + r) / 2;
        build(node * 2, l, mid); build(node * 2 + 1, mid + 1, r);
    }
}

void update(int pos, ll val, int node = 1, int l = 1, int r = n) {
    if (l == r) segtree[node] = val;
    else {
        int mid = (l + r) / 2;
        if (pos > mid) update(pos, val, node * 2 + 1, mid + 1, r);
        else update(pos, val, node * 2, l, mid);
        segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]);
    }
}

ll query(int x, int y, int node = 1, int l = 1, int r = n) {
    if (l > y || r < x) return INT_MIN;
    if (l >= x && r <= y) return segtree[node];
    int mid = (l + r) / 2;
    return max(query(x, y, node * 2, l, mid), query(x, y, node * 2 + 1, mid + 1, r));
}

void solve() {
    build();
    for (int i = 1; i <= n; i++) {
        for (int j : ins[i]) update(j, h[j]);
        ans[i] = max(ans[i], query(i - b[i], i - a[i]) - h[i]);
        for (int j : rem[i]) update(j, INT_MIN);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> a[i] >> b[i];
        ins[i + a[i]].push_back(i);
        rem[i + b[i]].push_back(i);
    }
    int q;
    cin >> q;
    if (q == 1) {
        memset(ans, -1, sizeof ans);
        solve();
        for (int i = 1; i <= n; i++) h[i] *= -1;
        solve();
        cout << *max_element(ans + 1, ans + n + 1);
    } else {
        cout << "TODO :(";
    }
    return 0;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 19200 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 325 ms 39160 KB Output is correct
2 Correct 378 ms 41600 KB Output is correct
3 Correct 261 ms 36564 KB Output is correct
4 Correct 404 ms 41704 KB Output is correct
5 Correct 158 ms 30328 KB Output is correct
6 Correct 392 ms 41608 KB Output is correct
7 Correct 342 ms 39288 KB Output is correct
8 Correct 395 ms 41464 KB Output is correct
9 Correct 55 ms 23928 KB Output is correct
10 Correct 370 ms 41464 KB Output is correct
11 Correct 228 ms 33256 KB Output is correct
12 Correct 380 ms 41488 KB Output is correct
13 Correct 249 ms 38176 KB Output is correct
14 Correct 222 ms 37408 KB Output is correct
15 Correct 215 ms 38136 KB Output is correct
16 Correct 213 ms 38776 KB Output is correct
17 Correct 232 ms 37748 KB Output is correct
18 Correct 214 ms 37624 KB Output is correct
19 Correct 223 ms 37700 KB Output is correct
20 Correct 218 ms 37700 KB Output is correct
21 Correct 225 ms 37728 KB Output is correct
22 Correct 229 ms 38132 KB Output is correct
23 Correct 232 ms 37624 KB Output is correct
24 Correct 207 ms 38516 KB Output is correct

Subtask #4
0 / 65.0

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