oj.uz

Submission #266434

# Submission time Handle Problem Language Result Execution time Memory
266434 2020-08-15T09:29:22 Z dolphingarlic Two Antennas (JOI19_antennas) C++14
22 / 100
 374 ms 38136 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]) update(j, h[j]);
        mx[i] = max(mx[i], query(i - b[i], i - a[i]) - h[i]);
        for (int j : rem[i]) 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];
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        Q[l].push_back({r, i});
    }
    for (int i = n; i; i--) {
        ins[i + a[i]].push_back(i);
        rem[i + b[i]].push_back(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:73:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for (int j = 0; j < Q[i].size(); j++) {
      |                             ~~^~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24704 KB Output is correct
2 Correct 26 ms 24704 KB Output is correct
3 Incorrect 30 ms 24704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24704 KB Output is correct
2 Correct 26 ms 24704 KB Output is correct
3 Incorrect 30 ms 24704 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 369 ms 36988 KB Output is correct
2 Correct 356 ms 38008 KB Output is correct
3 Correct 241 ms 34680 KB Output is correct
4 Correct 374 ms 38136 KB Output is correct
5 Correct 150 ms 30840 KB Output is correct
6 Correct 344 ms 38136 KB Output is correct
7 Correct 345 ms 36632 KB Output is correct
8 Correct 346 ms 38136 KB Output is correct
9 Correct 54 ms 26616 KB Output is correct
10 Correct 347 ms 38116 KB Output is correct
11 Correct 206 ms 33036 KB Output is correct
12 Correct 339 ms 38008 KB Output is correct
13 Correct 230 ms 34672 KB Output is correct
14 Correct 222 ms 34036 KB Output is correct
15 Correct 215 ms 34808 KB Output is correct
16 Correct 192 ms 35448 KB Output is correct
17 Correct 237 ms 34588 KB Output is correct
18 Correct 216 ms 34296 KB Output is correct
19 Correct 229 ms 34416 KB Output is correct
20 Correct 219 ms 34676 KB Output is correct
21 Correct 228 ms 34340 KB Output is correct
22 Correct 232 ms 34640 KB Output is correct
23 Correct 225 ms 34296 KB Output is correct
24 Correct 191 ms 35064 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24704 KB Output is correct
2 Correct 26 ms 24704 KB Output is correct
3 Incorrect 30 ms 24704 KB Output isn't correct
4 Halted 0 ms 0 KB -