Submission #796284

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
796284	2023-07-28T08:50:38 Z	finn__	Tourism (JOI23_tourism)	C++17	7 / 100	52 ms	9448 KB

tourism

#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 100000, LGN = 18;

size_t tree[1 << (LGN + 1)][2];

void build()
{
    for (size_t i = (1 << LGN) - 1; i; --i)
    {
        tree[i][0] = min(tree[i << 1][0], tree[i << 1 | 1][0]);
        tree[i][1] = max(tree[i << 1][1], tree[i << 1 | 1][1]);
    }
}

pair<size_t, size_t> range_min_max(size_t i, size_t j)
{
    i += 1 << LGN, j += 1 << LGN;
    size_t x = SIZE_MAX, y = 0;
    while (i <= j)
    {
        if (i & 1)
        {
            x = min(x, tree[i][0]);
            y = max(y, tree[i++][1]);
        }
        if (!(j & 1))
        {
            x = min(x, tree[j][0]);
            y = max(y, tree[j--][1]);
        }
        i >>= 1;
        j >>= 1;
    }
    return {x, y};
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, m, q;
    cin >> n >> m >> q;

    for (size_t i = 0; i < n - 1; ++i)
    {
        size_t u, v;
        cin >> u >> v;
    }

    for (size_t i = 0; i < m; ++i)
        cin >> tree[(1 << LGN) + i][0], tree[(1 << LGN) + i][1] = tree[(1 << LGN) + i][0];
    build();

    while (q--)
    {
        size_t l, r;
        cin >> l >> r, --l, --r;
        auto [a, b] = range_min_max(l, r);
        cout << b - a + 1 << '\n';
    }
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	4352 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	4352 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4308 KB	Output is correct
2	Correct	3 ms	4436 KB	Output is correct
3	Correct	3 ms	4436 KB	Output is correct
4	Correct	37 ms	6792 KB	Output is correct
5	Correct	33 ms	7628 KB	Output is correct
6	Correct	32 ms	8140 KB	Output is correct
7	Correct	48 ms	9448 KB	Output is correct
8	Correct	48 ms	9364 KB	Output is correct
9	Correct	52 ms	9388 KB	Output is correct
10	Correct	48 ms	9448 KB	Output is correct
11	Correct	47 ms	9388 KB	Output is correct
12	Correct	42 ms	9224 KB	Output is correct
13	Correct	42 ms	9164 KB	Output is correct
14	Correct	42 ms	9212 KB	Output is correct
15	Correct	25 ms	6104 KB	Output is correct
16	Correct	36 ms	9008 KB	Output is correct
17	Correct	35 ms	7460 KB	Output is correct