oj.uz

답안 #266431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
266431 2020-08-15T09:23:50 Z dolphingarlic Two Antennas (JOI19_antennas) C++14
22 / 100
 438 ms 41848 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int oo = 1e9;

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

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(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, 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;
    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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 25472 KB Output is correct
2 Correct 30 ms 25472 KB Output is correct
3 Incorrect 32 ms 25472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 25472 KB Output is correct
2 Correct 30 ms 25472 KB Output is correct
3 Incorrect 32 ms 25472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 344 ms 40568 KB Output is correct
2 Correct 372 ms 41720 KB Output is correct
3 Correct 247 ms 38224 KB Output is correct
4 Correct 370 ms 41720 KB Output is correct
5 Correct 158 ms 33016 KB Output is correct
6 Correct 376 ms 41848 KB Output is correct
7 Correct 317 ms 40096 KB Output is correct
8 Correct 415 ms 41848 KB Output is correct
9 Correct 57 ms 27768 KB Output is correct
10 Correct 438 ms 41632 KB Output is correct
11 Correct 236 ms 35064 KB Output is correct
12 Correct 410 ms 41720 KB Output is correct
13 Correct 244 ms 38388 KB Output is correct
14 Correct 230 ms 37664 KB Output is correct
15 Correct 218 ms 38392 KB Output is correct
16 Correct 200 ms 39088 KB Output is correct
17 Correct 236 ms 38004 KB Output is correct
18 Correct 215 ms 38008 KB Output is correct
19 Correct 220 ms 37968 KB Output is correct
20 Correct 222 ms 37956 KB Output is correct
21 Correct 243 ms 37944 KB Output is correct
22 Correct 230 ms 38260 KB Output is correct
23 Correct 224 ms 37876 KB Output is correct
24 Correct 199 ms 38772 KB Output is correct

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 25472 KB Output is correct
2 Correct 30 ms 25472 KB Output is correct
3 Incorrect 32 ms 25472 KB Output isn't correct
4 Halted 0 ms 0 KB -