oj.uz

답안 #867001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867001 2023-10-27T14:58:43 Z lolismek Two Antennas (JOI19_antennas) C++14
100 / 100
 807 ms 40240 KB 
#include <iostream>
#include <vector>

#define pii pair <int, int>

using namespace std;

const int NMAX = 2e5;
const int INF = 1e9 + 10; // ?

int n, q;
int v[NMAX + 1];
pii ant[NMAX + 1];
pii quer[NMAX + 1];

vector <int> inds[NMAX + 1];
vector <pii> ev[NMAX + 1];

int qans[NMAX + 1];

namespace AINT{
    struct Node{
        int maxi, mini, diff;
    }seg[4 * NMAX + 1];

    void propag(int node, int l, int r){
        int x = seg[node].mini;
        seg[node].mini = +INF;
        // ^ singe-handedly the most important aspect of the Segment Tree
        // makes sure that a minimum finds a maximum, but not a maximum finds a minimum

        if(l < r){
            seg[2 * node].mini = min(seg[2 * node].mini, x);
            seg[2 * node].diff = max(seg[2 * node].diff, seg[2 * node].maxi - seg[2 * node].mini);

            seg[2 * node + 1].mini = min(seg[2 * node + 1].mini, x);
            seg[2 * node + 1].diff = max(seg[2 * node + 1].diff, seg[2 * node + 1].maxi - seg[2 * node + 1].mini);
        }
    }

    void build(int node, int l, int r){
        seg[node].maxi = -INF;
        seg[node].mini = +INF;
        seg[node].diff = seg[node].maxi - seg[node].mini;

        if(l == r){
            return;
        }

        int mid = (l + r) / 2;
        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);
    }

    void updatemx(int node, int l, int r, int pos, int val){
        propag(node, l, r);
        if(l == r){
            seg[node].maxi = val;
            seg[node].mini = +INF;
            seg[node].diff = max(seg[node].diff, seg[node].maxi - seg[node].mini);
            return;
        }

        int mid = (l + r) / 2;
        if(pos <= mid){
            updatemx(2 * node, l, mid, pos, val);
        }else{
            updatemx(2 * node + 1, mid + 1, r, pos, val);
        }

        propag(2 * node, l, mid);
        propag(2 * node + 1, mid + 1, r);

        seg[node].maxi = max(seg[2 * node].maxi, seg[2 * node + 1].maxi);
        seg[node].diff = max(seg[2 * node].diff, seg[2 * node + 1].diff);
    }

    void updatemn(int node, int l, int r, int ul, int ur, int val){
        propag(node, l, r);
        if(ul <= l && r <= ur){
            seg[node].mini = min(val, seg[node].mini);
            seg[node].diff = max(seg[node].diff, seg[node].maxi - seg[node].mini);
            return;
        }

        int mid = (l + r) / 2;
        if(ul <= mid){
            updatemn(2 * node, l, mid, ul, ur, val);
        }
        if(mid + 1 <= ur){
            updatemn(2 * node + 1, mid + 1, r, ul, ur, val);
        }

        propag(2 * node, l, mid);
        propag(2 * node + 1, mid + 1, r);

        seg[node].mini = max(seg[2 * node].mini, seg[2 * node + 1].mini);
        seg[node].diff = max(seg[2 * node].diff, seg[2 * node + 1].diff);
    }

    int query(int node, int l, int r, int ql, int qr){
        propag(node, l, r);
        if(ql <= l && r <= qr){
            return seg[node].diff;
        }

        int mid = (l + r) / 2, ans = -INF;
        if(ql <= mid){
            ans = max(ans, query(2 * node, l, mid, ql, qr));
        }
        if(mid + 1 <= qr){
            ans = max(ans, query(2 * node + 1, mid + 1, r, ql, qr));
        }

        return ans;
    }

    int querym(int node, int l, int r, int ql, int qr){
        propag(node, l, r);
        if(ql <= l && r <= qr){
            return seg[node].maxi;
        }

        int mid = (l + r) / 2, ans = -INF;
        if(ql <= mid){
            ans = max(ans, querym(2 * node, l, mid, ql, qr));
        }
        if(mid + 1 <= qr){
            ans = max(ans, querym(2 * node + 1, mid + 1, r, ql, qr));
        }

        return ans;
    }
}

void solve(){
    // clears
    for(int i = 1; i <= n; i++){
        ev[i].clear();
        inds[i].clear();
    }

    for(int i = 1; i <= n; i++){
        if(i + ant[i].first <= n){
            ev[i + ant[i].first].push_back({i, +1});
        }
        if(i + ant[i].second + 1 <= n){
            ev[i + ant[i].second + 1].push_back({i, -1});
        }
    }
    AINT::build(1, 1, n);

    for(int i = 1; i <= q; i++){
        inds[quer[i].second].push_back(i);
    }

    for(int i = 1; i <= n; i++){
        // process events
        for(pii e : ev[i]){
            if(e.second == +1){
                AINT::updatemx(1, 1, n, e.first, v[e.first]);
            }else{
                AINT::updatemx(1, 1, n, e.first, -INF);
            }
        }
        // update with current element
        if(i - ant[i].first >= 1){
            AINT::updatemn(1, 1, n, max(1, i - ant[i].second), i - ant[i].first, v[i]);
        }
        // answer queries
        for(int ind : inds[i]){
            qans[ind] = max(qans[ind], AINT::query(1, 1, n, quer[ind].first, quer[ind].second));
        }
    }
}

int main(){

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
        cin >> ant[i].first >> ant[i].second;
    }

    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> quer[i].first >> quer[i].second;
        qans[i] = -1;
    }

    solve();

    // reverse
    for(int i = 1; i <= n / 2; i++){
        swap(v[i], v[n - i + 1]);
        swap(ant[i], ant[n - i + 1]);
    }
    for(int i = 1; i <= q; i++){
        quer[i].first = n - quer[i].first + 1;
        quer[i].second = n - quer[i].second + 1;
        swap(quer[i].first, quer[i].second);
    }

    solve();

    for(int i = 1; i <= q; i++){
        cout << qans[i] << '\n';
    }

    return 0;
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14688 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14776 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14772 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14944 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 3 ms 14684 KB Output is correct
22 Correct 3 ms 14680 KB Output is correct
23 Correct 3 ms 14684 KB Output is correct
24 Correct 3 ms 14796 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14688 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14776 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14772 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14944 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 3 ms 14684 KB Output is correct
22 Correct 3 ms 14680 KB Output is correct
23 Correct 3 ms 14684 KB Output is correct
24 Correct 3 ms 14796 KB Output is correct
25 Correct 115 ms 17300 KB Output is correct
26 Correct 18 ms 14936 KB Output is correct
27 Correct 170 ms 18128 KB Output is correct
28 Correct 174 ms 18124 KB Output is correct
29 Correct 114 ms 17236 KB Output is correct
30 Correct 122 ms 17084 KB Output is correct
31 Correct 133 ms 17612 KB Output is correct
32 Correct 170 ms 18004 KB Output is correct
33 Correct 161 ms 18256 KB Output is correct
34 Correct 86 ms 16464 KB Output is correct
35 Correct 165 ms 18260 KB Output is correct
36 Correct 174 ms 18092 KB Output is correct
37 Correct 99 ms 16212 KB Output is correct
38 Correct 203 ms 17084 KB Output is correct
39 Correct 35 ms 15072 KB Output is correct
40 Correct 172 ms 17364 KB Output is correct
41 Correct 129 ms 16548 KB Output is correct
42 Correct 176 ms 17104 KB Output is correct
43 Correct 60 ms 15696 KB Output is correct
44 Correct 193 ms 17148 KB Output is correct
45 Correct 35 ms 15212 KB Output is correct
46 Correct 181 ms 17104 KB Output is correct
47 Correct 51 ms 15460 KB Output is correct
48 Correct 198 ms 17240 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 436 ms 29528 KB Output is correct
2 Correct 486 ms 30804 KB Output is correct
3 Correct 336 ms 27880 KB Output is correct
4 Correct 483 ms 30808 KB Output is correct
5 Correct 192 ms 23468 KB Output is correct
6 Correct 475 ms 30800 KB Output is correct
7 Correct 439 ms 29344 KB Output is correct
8 Correct 506 ms 30640 KB Output is correct
9 Correct 59 ms 18280 KB Output is correct
10 Correct 529 ms 30816 KB Output is correct
11 Correct 286 ms 24916 KB Output is correct
12 Correct 494 ms 30800 KB Output is correct
13 Correct 409 ms 30908 KB Output is correct
14 Correct 397 ms 30596 KB Output is correct
15 Correct 384 ms 29856 KB Output is correct
16 Correct 366 ms 29808 KB Output is correct
17 Correct 424 ms 31548 KB Output is correct
18 Correct 385 ms 30376 KB Output is correct
19 Correct 408 ms 30828 KB Output is correct
20 Correct 385 ms 30648 KB Output is correct
21 Correct 381 ms 30652 KB Output is correct
22 Correct 377 ms 30468 KB Output is correct
23 Correct 426 ms 30912 KB Output is correct
24 Correct 371 ms 29320 KB Output is correct

Subtask #4
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14688 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14776 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14772 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14944 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 3 ms 14684 KB Output is correct
22 Correct 3 ms 14680 KB Output is correct
23 Correct 3 ms 14684 KB Output is correct
24 Correct 3 ms 14796 KB Output is correct
25 Correct 115 ms 17300 KB Output is correct
26 Correct 18 ms 14936 KB Output is correct
27 Correct 170 ms 18128 KB Output is correct
28 Correct 174 ms 18124 KB Output is correct
29 Correct 114 ms 17236 KB Output is correct
30 Correct 122 ms 17084 KB Output is correct
31 Correct 133 ms 17612 KB Output is correct
32 Correct 170 ms 18004 KB Output is correct
33 Correct 161 ms 18256 KB Output is correct
34 Correct 86 ms 16464 KB Output is correct
35 Correct 165 ms 18260 KB Output is correct
36 Correct 174 ms 18092 KB Output is correct
37 Correct 99 ms 16212 KB Output is correct
38 Correct 203 ms 17084 KB Output is correct
39 Correct 35 ms 15072 KB Output is correct
40 Correct 172 ms 17364 KB Output is correct
41 Correct 129 ms 16548 KB Output is correct
42 Correct 176 ms 17104 KB Output is correct
43 Correct 60 ms 15696 KB Output is correct
44 Correct 193 ms 17148 KB Output is correct
45 Correct 35 ms 15212 KB Output is correct
46 Correct 181 ms 17104 KB Output is correct
47 Correct 51 ms 15460 KB Output is correct
48 Correct 198 ms 17240 KB Output is correct
49 Correct 436 ms 29528 KB Output is correct
50 Correct 486 ms 30804 KB Output is correct
51 Correct 336 ms 27880 KB Output is correct
52 Correct 483 ms 30808 KB Output is correct
53 Correct 192 ms 23468 KB Output is correct
54 Correct 475 ms 30800 KB Output is correct
55 Correct 439 ms 29344 KB Output is correct
56 Correct 506 ms 30640 KB Output is correct
57 Correct 59 ms 18280 KB Output is correct
58 Correct 529 ms 30816 KB Output is correct
59 Correct 286 ms 24916 KB Output is correct
60 Correct 494 ms 30800 KB Output is correct
61 Correct 409 ms 30908 KB Output is correct
62 Correct 397 ms 30596 KB Output is correct
63 Correct 384 ms 29856 KB Output is correct
64 Correct 366 ms 29808 KB Output is correct
65 Correct 424 ms 31548 KB Output is correct
66 Correct 385 ms 30376 KB Output is correct
67 Correct 408 ms 30828 KB Output is correct
68 Correct 385 ms 30648 KB Output is correct
69 Correct 381 ms 30652 KB Output is correct
70 Correct 377 ms 30468 KB Output is correct
71 Correct 426 ms 30912 KB Output is correct
72 Correct 371 ms 29320 KB Output is correct
73 Correct 615 ms 37124 KB Output is correct
74 Correct 467 ms 31824 KB Output is correct
75 Correct 575 ms 36148 KB Output is correct
76 Correct 807 ms 40240 KB Output is correct
77 Correct 385 ms 29352 KB Output is correct
78 Correct 646 ms 37968 KB Output is correct
79 Correct 659 ms 38488 KB Output is correct
80 Correct 730 ms 40004 KB Output is correct
81 Correct 280 ms 24864 KB Output is correct
82 Correct 605 ms 36304 KB Output is correct
83 Correct 555 ms 33136 KB Output is correct
84 Correct 739 ms 40096 KB Output is correct
85 Correct 615 ms 36616 KB Output is correct
86 Correct 686 ms 38936 KB Output is correct
87 Correct 423 ms 31676 KB Output is correct
88 Correct 678 ms 37960 KB Output is correct
89 Correct 641 ms 38072 KB Output is correct
90 Correct 712 ms 38844 KB Output is correct
91 Correct 505 ms 34668 KB Output is correct
92 Correct 688 ms 38980 KB Output is correct
93 Correct 420 ms 32680 KB Output is correct
94 Correct 704 ms 38840 KB Output is correct
95 Correct 473 ms 33752 KB Output is correct
96 Correct 641 ms 37556 KB Output is correct