Submission #796284

#	Time	Username	Problem	Language	Result	Execution time	Memory
796284		finn__	Tourism (JOI23_tourism)	C++17	7 / 100	52 ms	9448 KiB

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
• Subtask 2: 0 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41