oj.uz

Submission #266428

# Submission time Handle Problem Language Result Execution time Memory
266428 2020-08-15T09:18:36 Z dolphingarlic Two Antennas (JOI19_antennas) C++14
22 / 100
 377 ms 38520 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});
    }
    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:73: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]
   73 |         for (int j = 0; j < Q[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24576 KB Output is correct
2 Correct 26 ms 24724 KB Output is correct
3 Incorrect 26 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 19 ms 24576 KB Output is correct
2 Correct 26 ms 24724 KB Output is correct
3 Incorrect 26 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 313 ms 37352 KB Output is correct
2 Correct 346 ms 38264 KB Output is correct
3 Correct 238 ms 35064 KB Output is correct
4 Correct 364 ms 38264 KB Output is correct
5 Correct 153 ms 31224 KB Output is correct
6 Correct 345 ms 38392 KB Output is correct
7 Correct 307 ms 36728 KB Output is correct
8 Correct 360 ms 38408 KB Output is correct
9 Correct 54 ms 26872 KB Output is correct
10 Correct 356 ms 38520 KB Output is correct
11 Correct 221 ms 33016 KB Output is correct
12 Correct 377 ms 38264 KB Output is correct
13 Correct 253 ms 34932 KB Output is correct
14 Correct 223 ms 34208 KB Output is correct
15 Correct 229 ms 35072 KB Output is correct
16 Correct 198 ms 35576 KB Output is correct
17 Correct 241 ms 34676 KB Output is correct
18 Correct 217 ms 34680 KB Output is correct
19 Correct 222 ms 34512 KB Output is correct
20 Correct 219 ms 34628 KB Output is correct
21 Correct 228 ms 34524 KB Output is correct
22 Correct 232 ms 34932 KB Output is correct
23 Correct 238 ms 34548 KB Output is correct
24 Correct 197 ms 35188 KB Output is correct

Subtask #4
0 / 65.0

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