oj.uz

Submission #266432

# Submission time Handle Problem Language Result Execution time Memory
266432 2020-08-15T09:24:45 Z dolphingarlic Two Antennas (JOI19_antennas) C++14
22 / 100
 388 ms 39032 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int oo = 1e9;

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

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

void update(int pos, int 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]);
    }
}

int query(int x, int y, int node = 1, int l = 1, int r = n) {
    if (l > y || r < x) return -oo;
    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(int l, int r) {
    build();
    for (int i = l; i <= r; i++) {
        for (int j : ins[i]) if (l <= j && j <= r) update(j, h[j]);
        mx[i] = max(mx[i], query(i - b[i], i - a[i]) - h[i]);
        for (int j : rem[i]) if (l <= j && j <= r) update(j, -oo);
    }
}

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;
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        Q[l].push_back({r, i});
    }
    memset(ans, -1, sizeof ans);
    for (int i = 1; i <= n; i++) if (Q[i].size()) {
        sort(Q[i].begin(), Q[i].end());
        memset(mx, -1, sizeof mx);
        
        solve(i, n);
        for (int j = i; j <= n; j++) h[j] *= -1;

        solve(i, n);
        for (int j = i; j <= n; j++) h[j] *= -1;

        for (int j = 0; j < Q[i].size(); j++) {
            if (!j) ans[Q[i][j].second] = *max_element(mx + i, mx + Q[i][j].first + 1);
            else ans[Q[i][j].second] = max(ans[Q[i][j - 1].second], *max_element(mx + Q[i][j - 1].first + 1, mx + Q[i][j].first + 1));
        }
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return 0;
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int j = 0; j < Q[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 25472 KB Output is correct
2 Correct 27 ms 25472 KB Output is correct
3 Incorrect 27 ms 25472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 25472 KB Output is correct
2 Correct 27 ms 25472 KB Output is correct
3 Incorrect 27 ms 25472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 37768 KB Output is correct
2 Correct 357 ms 38776 KB Output is correct
3 Correct 259 ms 35612 KB Output is correct
4 Correct 355 ms 39032 KB Output is correct
5 Correct 145 ms 31736 KB Output is correct
6 Correct 361 ms 38908 KB Output is correct
7 Correct 303 ms 37336 KB Output is correct
8 Correct 388 ms 38904 KB Output is correct
9 Correct 54 ms 27520 KB Output is correct
10 Correct 351 ms 38776 KB Output is correct
11 Correct 216 ms 33656 KB Output is correct
12 Correct 363 ms 38904 KB Output is correct
13 Correct 262 ms 35444 KB Output is correct
14 Correct 228 ms 34848 KB Output is correct
15 Correct 219 ms 35576 KB Output is correct
16 Correct 201 ms 36216 KB Output is correct
17 Correct 238 ms 35188 KB Output is correct
18 Correct 216 ms 35068 KB Output is correct
19 Correct 228 ms 35020 KB Output is correct
20 Correct 228 ms 35268 KB Output is correct
21 Correct 238 ms 35288 KB Output is correct
22 Correct 229 ms 35480 KB Output is correct
23 Correct 230 ms 35188 KB Output is correct
24 Correct 198 ms 35700 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 25472 KB Output is correct
2 Correct 27 ms 25472 KB Output is correct
3 Incorrect 27 ms 25472 KB Output isn't correct
4 Halted 0 ms 0 KB -