oj.uz

Submission #718065

# Submission time Handle Problem Language Result Execution time Memory
718065 2023-04-03T09:26:50 Z Johann Two Antennas (JOI19_antennas) C++14
100 / 100
 526 ms 38080 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vpii vector<pii>
#define vtiii vector<tiii>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

struct item
{
    int res = -1;
    int ap = INT_MIN, an = INT_MIN; // apply operation
    int bp = INT_MAX, bn = INT_MAX; // what is contained in the Stuff
};

struct SegTree
{
    int size;
    vector<item> arr;
    void init(vi &H)
    {
        size = 1;
        while (size < sz(H))
            size *= 2;
        arr.assign(2 * size, item());
    }
    void combine(int x)
    {
        assert(arr[x].ap == INT_MIN && arr[x].an == INT_MIN);
        assert(x < size);
        arr[x].res = max(arr[2 * x].res, arr[2 * x + 1].res);
        arr[x].bp = min(arr[2 * x].bp, arr[2 * x + 1].bp);
        arr[x].bn = min(arr[2 * x].bn, arr[2 * x + 1].bn);
    }
    void apply(int x, int ap, int an)
    {
        arr[x].ap = max(arr[x].ap, ap);
        arr[x].an = max(arr[x].an, an);
        if (arr[x].ap != INT_MIN && arr[x].bp != INT_MAX)
            arr[x].res = max(arr[x].res, arr[x].ap - arr[x].bp);
        if (arr[x].an != INT_MIN && arr[x].bn != INT_MAX)
            arr[x].res = max(arr[x].res, arr[x].an - arr[x].bn);
    }
    void propagate(int x)
    {
        if (x < size)
            apply(2 * x, arr[x].ap, arr[x].an), apply(2 * x + 1, arr[x].ap, arr[x].an);
        arr[x].ap = arr[x].an = INT_MIN;
    }
    void update(int i, int bp, int bn, int x, int lx, int rx)
    {
        if (rx - lx == 1)
        {
            arr[x].ap = arr[x].an = INT_MIN;
            arr[x].bp = bp, arr[x].bn = bn;
            return;
        }
        propagate(x);
        int m = (lx + rx) / 2;
        if (i < m)
            update(i, bp, bn, 2 * x, lx, m);
        else
            update(i, bp, bn, 2 * x + 1, m, rx);
        combine(x);
    }
    void update(int i, int bp, int bn)
    {
        update(i, bp, bn, 1, 0, size);
    }
    void applyA(int l, int r, int ap, int an)
    {
        applyA(l, r, ap, an, 1, 0, size);
    }
    void applyA(int l, int r, int ap, int an, int x, int lx, int rx)
    {
        if (rx <= l || r <= lx)
            return;
        if (l <= lx && rx <= r)
        {
            apply(x, ap, an);
            return;
        }
        propagate(x);
        int m = (lx + rx) / 2;
        applyA(l, r, ap, an, 2 * x, lx, m);
        applyA(l, r, ap, an, 2 * x + 1, m, rx);
        combine(x);
    }
    int query(int l, int r, int x, int lx, int rx)
    {
        if (rx <= l || r <= lx)
            return -1;
        if (l <= lx && rx <= r)
            return arr[x].res;
        propagate(x);
        int m = (lx + rx) / 2;
        int a = query(l, r, 2 * x, lx, m);
        int b = query(l, r, 2 * x + 1, m, rx);
        return max(a, b);
    }
    int query(int l, int r)
    {
        return query(l, r, 1, 0, size);
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    vi H(n), A(n), B(n);
    vvi toAct(n + 1);
    vvi toDea(n + 1);
    for (int i = 0; i < n; ++i)
    {
        cin >> H[i] >> A[i] >> B[i];
        if (i + A[i] < n)
            toAct[i + A[i]].push_back(i);
        if (i + B[i] + 1 < n)
            toDea[i + B[i] + 1].push_back(i);
    }

    int q;
    cin >> q;
    vtiii Q(q);
    for (int i = 0, l, r; i < q; ++i)
    {
        cin >> l >> r;
        --l, --r;
        Q[i] = {l, r, i};
    }
    sort(all(Q), [&](tiii &a, tiii &b)
         { return get<1>(a) > get<1>(b); }); // Niedrige Endpunkte nach hinten, dann kann man den Vektor als queue verwenden
    vi ans(q, -1);

    SegTree seg;
    seg.init(H);

    vb active(n, false);
    for (int i = 0; i < n; ++i)
    {
        for (int j : toAct[i])
            seg.update(j, H[j], -H[j]);
        for (int j : toDea[i])
            seg.update(j, INT_MAX, INT_MAX);

        seg.applyA(i - B[i], i - A[i] + 1, H[i], -H[i]);

        while (!Q.empty() && get<1>(Q.back()) == i)
        {
            int l, r, idx;
            tie(l, r, idx) = Q.back();
            Q.pop_back();
            ans[idx] = seg.query(l, r);
        }
    }

    for (int x : ans)
        cout << x << "\n";
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 324 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 324 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 72 ms 5064 KB Output is correct
26 Correct 11 ms 980 KB Output is correct
27 Correct 106 ms 7136 KB Output is correct
28 Correct 115 ms 7280 KB Output is correct
29 Correct 71 ms 5060 KB Output is correct
30 Correct 79 ms 4964 KB Output is correct
31 Correct 91 ms 6348 KB Output is correct
32 Correct 112 ms 7244 KB Output is correct
33 Correct 101 ms 6684 KB Output is correct
34 Correct 61 ms 3724 KB Output is correct
35 Correct 110 ms 7080 KB Output is correct
36 Correct 112 ms 7284 KB Output is correct
37 Correct 63 ms 3832 KB Output is correct
38 Correct 100 ms 6188 KB Output is correct
39 Correct 17 ms 1356 KB Output is correct
40 Correct 103 ms 6284 KB Output is correct
41 Correct 79 ms 4680 KB Output is correct
42 Correct 114 ms 6280 KB Output is correct
43 Correct 36 ms 2320 KB Output is correct
44 Correct 100 ms 6276 KB Output is correct
45 Correct 19 ms 1492 KB Output is correct
46 Correct 108 ms 6212 KB Output is correct
47 Correct 35 ms 1924 KB Output is correct
48 Correct 107 ms 6340 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 24352 KB Output is correct
2 Correct 284 ms 30416 KB Output is correct
3 Correct 177 ms 24472 KB Output is correct
4 Correct 293 ms 30424 KB Output is correct
5 Correct 137 ms 14412 KB Output is correct
6 Correct 263 ms 30412 KB Output is correct
7 Correct 225 ms 27856 KB Output is correct
8 Correct 290 ms 30376 KB Output is correct
9 Correct 43 ms 4812 KB Output is correct
10 Correct 282 ms 30432 KB Output is correct
11 Correct 166 ms 17764 KB Output is correct
12 Correct 296 ms 30340 KB Output is correct
13 Correct 193 ms 27808 KB Output is correct
14 Correct 167 ms 27888 KB Output is correct
15 Correct 170 ms 27968 KB Output is correct
16 Correct 188 ms 28476 KB Output is correct
17 Correct 205 ms 27968 KB Output is correct
18 Correct 178 ms 28472 KB Output is correct
19 Correct 191 ms 27732 KB Output is correct
20 Correct 194 ms 27840 KB Output is correct
21 Correct 199 ms 27568 KB Output is correct
22 Correct 170 ms 27852 KB Output is correct
23 Correct 186 ms 27984 KB Output is correct
24 Correct 182 ms 28020 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 324 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 72 ms 5064 KB Output is correct
26 Correct 11 ms 980 KB Output is correct
27 Correct 106 ms 7136 KB Output is correct
28 Correct 115 ms 7280 KB Output is correct
29 Correct 71 ms 5060 KB Output is correct
30 Correct 79 ms 4964 KB Output is correct
31 Correct 91 ms 6348 KB Output is correct
32 Correct 112 ms 7244 KB Output is correct
33 Correct 101 ms 6684 KB Output is correct
34 Correct 61 ms 3724 KB Output is correct
35 Correct 110 ms 7080 KB Output is correct
36 Correct 112 ms 7284 KB Output is correct
37 Correct 63 ms 3832 KB Output is correct
38 Correct 100 ms 6188 KB Output is correct
39 Correct 17 ms 1356 KB Output is correct
40 Correct 103 ms 6284 KB Output is correct
41 Correct 79 ms 4680 KB Output is correct
42 Correct 114 ms 6280 KB Output is correct
43 Correct 36 ms 2320 KB Output is correct
44 Correct 100 ms 6276 KB Output is correct
45 Correct 19 ms 1492 KB Output is correct
46 Correct 108 ms 6212 KB Output is correct
47 Correct 35 ms 1924 KB Output is correct
48 Correct 107 ms 6340 KB Output is correct
49 Correct 239 ms 24352 KB Output is correct
50 Correct 284 ms 30416 KB Output is correct
51 Correct 177 ms 24472 KB Output is correct
52 Correct 293 ms 30424 KB Output is correct
53 Correct 137 ms 14412 KB Output is correct
54 Correct 263 ms 30412 KB Output is correct
55 Correct 225 ms 27856 KB Output is correct
56 Correct 290 ms 30376 KB Output is correct
57 Correct 43 ms 4812 KB Output is correct
58 Correct 282 ms 30432 KB Output is correct
59 Correct 166 ms 17764 KB Output is correct
60 Correct 296 ms 30340 KB Output is correct
61 Correct 193 ms 27808 KB Output is correct
62 Correct 167 ms 27888 KB Output is correct
63 Correct 170 ms 27968 KB Output is correct
64 Correct 188 ms 28476 KB Output is correct
65 Correct 205 ms 27968 KB Output is correct
66 Correct 178 ms 28472 KB Output is correct
67 Correct 191 ms 27732 KB Output is correct
68 Correct 194 ms 27840 KB Output is correct
69 Correct 199 ms 27568 KB Output is correct
70 Correct 170 ms 27852 KB Output is correct
71 Correct 186 ms 27984 KB Output is correct
72 Correct 182 ms 28020 KB Output is correct
73 Correct 394 ms 34124 KB Output is correct
74 Correct 310 ms 30912 KB Output is correct
75 Correct 410 ms 32028 KB Output is correct
76 Correct 471 ms 38072 KB Output is correct
77 Correct 244 ms 19936 KB Output is correct
78 Correct 393 ms 35496 KB Output is correct
79 Correct 390 ms 35420 KB Output is correct
80 Correct 526 ms 38080 KB Output is correct
81 Correct 200 ms 11692 KB Output is correct
82 Correct 411 ms 34068 KB Output is correct
83 Correct 351 ms 25360 KB Output is correct
84 Correct 503 ms 38072 KB Output is correct
85 Correct 312 ms 31544 KB Output is correct
86 Correct 413 ms 34400 KB Output is correct
87 Correct 243 ms 28768 KB Output is correct
88 Correct 454 ms 34948 KB Output is correct
89 Correct 373 ms 32748 KB Output is correct
90 Correct 404 ms 34972 KB Output is correct
91 Correct 250 ms 29892 KB Output is correct
92 Correct 469 ms 34368 KB Output is correct
93 Correct 228 ms 28532 KB Output is correct
94 Correct 371 ms 34440 KB Output is correct
95 Correct 246 ms 29420 KB Output is correct
96 Correct 335 ms 34552 KB Output is correct