oj.uz

Submission #708285

# Submission time Handle Problem Language Result Execution time Memory
708285 2023-03-11T13:54:02 Z LittleCube Two Antennas (JOI19_antennas) C++14
100 / 100
 739 ms 66052 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const ll inf = 4'000'000'000;
const pll emp = {inf, -inf};
vector<pii> qu[200005];
vector<int> in[200005], out[200005];
int N, Q, A[200005], B[200005], H[200005];
ll ans[200005];

struct node
{
    ll res = -1;
    pll h = emp, l = emp;

    void applyH(ll H)
    {
        if (abs(H) == inf)
            return;
        h.F = min(h.F, H), h.S = max(h.S, H);
    }

} seg[800005];

node calc(node n)
{
    if (n.h != emp && n.l != emp)
        n.res = max({n.res,
                     abs(n.h.F - n.l.F),
                     abs(n.h.S - n.l.F),
                     abs(n.h.F - n.l.S),
                     abs(n.h.S - n.l.S)});
    return node{n.res, emp, n.l};
}

void push(int i)
{
    seg[i << 1].applyH(seg[i].h.F);
    seg[i << 1].applyH(seg[i].h.S);
    seg[i << 1 | 1].applyH(seg[i].h.F);
    seg[i << 1 | 1].applyH(seg[i].h.S);
    seg[i] = calc(seg[i]);
}

void pull(int i)
{
    seg[i].res = max({seg[i].res, calc(seg[i << 1]).res, calc(seg[i << 1 | 1]).res});
}

void toggle(int pos, ll h, bool on, int i = 1, int L = 1, int R = N)
{
    if (L == R)
    {
        if (on)
        {
            seg[i] = calc(seg[i]);
            seg[i].l = pll(h, h);
        }
        else
        {
            seg[i] = calc(seg[i]);
            seg[i].l = emp;
        }
    }
    else
    {
        int mid = (L + R) / 2;
        push(i);
        if (pos <= mid)
            toggle(pos, h, on, i << 1, L, mid);
        else
            toggle(pos, h, on, i << 1 | 1, mid + 1, R);
        pull(i);
        seg[i].l.F = min(seg[i << 1].l.F, seg[i << 1 | 1].l.F);
        seg[i].l.S = max(seg[i << 1].l.S, seg[i << 1 | 1].l.S);
    }
}

void modify(int mL, int mR, ll h, int i = 1, int L = 1, int R = N)
{
    if (mL <= L && R <= mR)
        seg[i].applyH(h);
    else if (R < mL || mR < L)
        return;
    else
    {
        int mid = (L + R) / 2;
        push(i);
        modify(mL, mR, h, i << 1, L, mid);
        modify(mL, mR, h, i << 1 | 1, mid + 1, R);
        pull(i);
    }
}

ll query(int mL, int mR, int i = 1, int L = 1, int R = N)
{
    if (mL <= L && R <= mR)
        return calc(seg[i]).res;
    else if (R < mL || mR < L)
        return -1;
    else
    {
        int mid = (L + R) / 2;
        push(i);
        return max(query(mL, mR, i << 1, L, mid),
                   query(mL, mR, i << 1 | 1, mid + 1, R));
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> H[i] >> A[i] >> B[i];
        if (i + A[i] <= N)
            in[i + A[i]].emplace_back(i);
        if (i + B[i] <= N)
            out[i + B[i]].emplace_back(i);
    }
    cin >> Q;
    for (int i = 1; i <= Q; i++)
    {
        int L, R;
        cin >> L >> R;
        qu[R].emplace_back(pii(i, L));
    }
    for (int i = 1; i <= N; i++)
    {
        for (auto j : in[i])
            toggle(j, H[j], 1);
        modify(max(0, i - B[i]), max(0, i - A[i]), H[i]);
        for (auto [j, L] : qu[i])
            ans[j] = query(L, i);
        for (auto j : out[i])
            toggle(j, H[j], 0);
    }
    for (int i = 1; i <= Q; i++)
        cout << ans[i] << '\n';
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:141:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |         for (auto [j, L] : qu[i])
      |                   ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 45652 KB Output is correct
2 Correct 21 ms 45732 KB Output is correct
3 Correct 20 ms 45652 KB Output is correct
4 Correct 21 ms 45752 KB Output is correct
5 Correct 21 ms 45692 KB Output is correct
6 Correct 20 ms 45696 KB Output is correct
7 Correct 20 ms 45780 KB Output is correct
8 Correct 20 ms 45772 KB Output is correct
9 Correct 20 ms 45644 KB Output is correct
10 Correct 20 ms 45696 KB Output is correct
11 Correct 21 ms 45756 KB Output is correct
12 Correct 21 ms 45656 KB Output is correct
13 Correct 20 ms 45700 KB Output is correct
14 Correct 20 ms 45688 KB Output is correct
15 Correct 20 ms 45732 KB Output is correct
16 Correct 19 ms 45652 KB Output is correct
17 Correct 20 ms 45676 KB Output is correct
18 Correct 20 ms 45740 KB Output is correct
19 Correct 20 ms 45736 KB Output is correct
20 Correct 20 ms 45652 KB Output is correct
21 Correct 22 ms 45652 KB Output is correct
22 Correct 20 ms 45732 KB Output is correct
23 Correct 20 ms 45732 KB Output is correct
24 Correct 21 ms 45724 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 45652 KB Output is correct
2 Correct 21 ms 45732 KB Output is correct
3 Correct 20 ms 45652 KB Output is correct
4 Correct 21 ms 45752 KB Output is correct
5 Correct 21 ms 45692 KB Output is correct
6 Correct 20 ms 45696 KB Output is correct
7 Correct 20 ms 45780 KB Output is correct
8 Correct 20 ms 45772 KB Output is correct
9 Correct 20 ms 45644 KB Output is correct
10 Correct 20 ms 45696 KB Output is correct
11 Correct 21 ms 45756 KB Output is correct
12 Correct 21 ms 45656 KB Output is correct
13 Correct 20 ms 45700 KB Output is correct
14 Correct 20 ms 45688 KB Output is correct
15 Correct 20 ms 45732 KB Output is correct
16 Correct 19 ms 45652 KB Output is correct
17 Correct 20 ms 45676 KB Output is correct
18 Correct 20 ms 45740 KB Output is correct
19 Correct 20 ms 45736 KB Output is correct
20 Correct 20 ms 45652 KB Output is correct
21 Correct 22 ms 45652 KB Output is correct
22 Correct 20 ms 45732 KB Output is correct
23 Correct 20 ms 45732 KB Output is correct
24 Correct 21 ms 45724 KB Output is correct
25 Correct 95 ms 51088 KB Output is correct
26 Correct 31 ms 46288 KB Output is correct
27 Correct 124 ms 53312 KB Output is correct
28 Correct 128 ms 53408 KB Output is correct
29 Correct 90 ms 51120 KB Output is correct
30 Correct 93 ms 50964 KB Output is correct
31 Correct 97 ms 52440 KB Output is correct
32 Correct 129 ms 53324 KB Output is correct
33 Correct 115 ms 53036 KB Output is correct
34 Correct 74 ms 49408 KB Output is correct
35 Correct 123 ms 53228 KB Output is correct
36 Correct 130 ms 53392 KB Output is correct
37 Correct 78 ms 49596 KB Output is correct
38 Correct 128 ms 52392 KB Output is correct
39 Correct 36 ms 46620 KB Output is correct
40 Correct 121 ms 52448 KB Output is correct
41 Correct 92 ms 50636 KB Output is correct
42 Correct 125 ms 52416 KB Output is correct
43 Correct 55 ms 47988 KB Output is correct
44 Correct 124 ms 52428 KB Output is correct
45 Correct 39 ms 46932 KB Output is correct
46 Correct 120 ms 52380 KB Output is correct
47 Correct 47 ms 47432 KB Output is correct
48 Correct 129 ms 52432 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 53032 KB Output is correct
2 Correct 423 ms 53616 KB Output is correct
3 Correct 288 ms 52984 KB Output is correct
4 Correct 413 ms 56136 KB Output is correct
5 Correct 180 ms 50284 KB Output is correct
6 Correct 419 ms 56112 KB Output is correct
7 Correct 465 ms 54728 KB Output is correct
8 Correct 514 ms 56128 KB Output is correct
9 Correct 73 ms 47320 KB Output is correct
10 Correct 425 ms 56112 KB Output is correct
11 Correct 252 ms 52172 KB Output is correct
12 Correct 440 ms 56092 KB Output is correct
13 Correct 222 ms 53648 KB Output is correct
14 Correct 212 ms 53620 KB Output is correct
15 Correct 204 ms 53812 KB Output is correct
16 Correct 186 ms 54228 KB Output is correct
17 Correct 216 ms 53884 KB Output is correct
18 Correct 201 ms 54228 KB Output is correct
19 Correct 208 ms 53508 KB Output is correct
20 Correct 202 ms 53724 KB Output is correct
21 Correct 212 ms 53512 KB Output is correct
22 Correct 213 ms 53716 KB Output is correct
23 Correct 209 ms 53576 KB Output is correct
24 Correct 179 ms 53652 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 45652 KB Output is correct
2 Correct 21 ms 45732 KB Output is correct
3 Correct 20 ms 45652 KB Output is correct
4 Correct 21 ms 45752 KB Output is correct
5 Correct 21 ms 45692 KB Output is correct
6 Correct 20 ms 45696 KB Output is correct
7 Correct 20 ms 45780 KB Output is correct
8 Correct 20 ms 45772 KB Output is correct
9 Correct 20 ms 45644 KB Output is correct
10 Correct 20 ms 45696 KB Output is correct
11 Correct 21 ms 45756 KB Output is correct
12 Correct 21 ms 45656 KB Output is correct
13 Correct 20 ms 45700 KB Output is correct
14 Correct 20 ms 45688 KB Output is correct
15 Correct 20 ms 45732 KB Output is correct
16 Correct 19 ms 45652 KB Output is correct
17 Correct 20 ms 45676 KB Output is correct
18 Correct 20 ms 45740 KB Output is correct
19 Correct 20 ms 45736 KB Output is correct
20 Correct 20 ms 45652 KB Output is correct
21 Correct 22 ms 45652 KB Output is correct
22 Correct 20 ms 45732 KB Output is correct
23 Correct 20 ms 45732 KB Output is correct
24 Correct 21 ms 45724 KB Output is correct
25 Correct 95 ms 51088 KB Output is correct
26 Correct 31 ms 46288 KB Output is correct
27 Correct 124 ms 53312 KB Output is correct
28 Correct 128 ms 53408 KB Output is correct
29 Correct 90 ms 51120 KB Output is correct
30 Correct 93 ms 50964 KB Output is correct
31 Correct 97 ms 52440 KB Output is correct
32 Correct 129 ms 53324 KB Output is correct
33 Correct 115 ms 53036 KB Output is correct
34 Correct 74 ms 49408 KB Output is correct
35 Correct 123 ms 53228 KB Output is correct
36 Correct 130 ms 53392 KB Output is correct
37 Correct 78 ms 49596 KB Output is correct
38 Correct 128 ms 52392 KB Output is correct
39 Correct 36 ms 46620 KB Output is correct
40 Correct 121 ms 52448 KB Output is correct
41 Correct 92 ms 50636 KB Output is correct
42 Correct 125 ms 52416 KB Output is correct
43 Correct 55 ms 47988 KB Output is correct
44 Correct 124 ms 52428 KB Output is correct
45 Correct 39 ms 46932 KB Output is correct
46 Correct 120 ms 52380 KB Output is correct
47 Correct 47 ms 47432 KB Output is correct
48 Correct 129 ms 52432 KB Output is correct
49 Correct 384 ms 53032 KB Output is correct
50 Correct 423 ms 53616 KB Output is correct
51 Correct 288 ms 52984 KB Output is correct
52 Correct 413 ms 56136 KB Output is correct
53 Correct 180 ms 50284 KB Output is correct
54 Correct 419 ms 56112 KB Output is correct
55 Correct 465 ms 54728 KB Output is correct
56 Correct 514 ms 56128 KB Output is correct
57 Correct 73 ms 47320 KB Output is correct
58 Correct 425 ms 56112 KB Output is correct
59 Correct 252 ms 52172 KB Output is correct
60 Correct 440 ms 56092 KB Output is correct
61 Correct 222 ms 53648 KB Output is correct
62 Correct 212 ms 53620 KB Output is correct
63 Correct 204 ms 53812 KB Output is correct
64 Correct 186 ms 54228 KB Output is correct
65 Correct 216 ms 53884 KB Output is correct
66 Correct 201 ms 54228 KB Output is correct
67 Correct 208 ms 53508 KB Output is correct
68 Correct 202 ms 53724 KB Output is correct
69 Correct 212 ms 53512 KB Output is correct
70 Correct 213 ms 53716 KB Output is correct
71 Correct 209 ms 53576 KB Output is correct
72 Correct 179 ms 53652 KB Output is correct
73 Correct 608 ms 62508 KB Output is correct
74 Correct 448 ms 56908 KB Output is correct
75 Correct 539 ms 62384 KB Output is correct
76 Correct 690 ms 66052 KB Output is correct
77 Correct 361 ms 57176 KB Output is correct
78 Correct 652 ms 63008 KB Output is correct
79 Correct 641 ms 64484 KB Output is correct
80 Correct 713 ms 65952 KB Output is correct
81 Correct 264 ms 55436 KB Output is correct
82 Correct 596 ms 61152 KB Output is correct
83 Correct 540 ms 61408 KB Output is correct
84 Correct 739 ms 65880 KB Output is correct
85 Correct 350 ms 58896 KB Output is correct
86 Correct 424 ms 62416 KB Output is correct
87 Correct 244 ms 55244 KB Output is correct
88 Correct 404 ms 62912 KB Output is correct
89 Correct 380 ms 60436 KB Output is correct
90 Correct 425 ms 62872 KB Output is correct
91 Correct 281 ms 56712 KB Output is correct
92 Correct 412 ms 62288 KB Output is correct
93 Correct 255 ms 55236 KB Output is correct
94 Correct 434 ms 62468 KB Output is correct
95 Correct 272 ms 56120 KB Output is correct
96 Correct 399 ms 62440 KB Output is correct