Submission #509814

#	Time	Username	Problem	Language	Result	Execution time	Memory
509814		KoD	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	349 ms	22320 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<int> L(N), R(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> L[i] >> R[i];
        R[i] += 1;
    }
    array<vector<int>, 20> parent = {};
    parent[0] = vector<int>(N + 1);
    parent[0][N] = N;
    {
        std::map<int, int> map;
        int r = N;
        for (int l = N - 1; l >= 0; --l) {
            while (true) {
                const auto itr = map.upper_bound(L[l]);
                if (itr != map.end() and itr->second < R[l]) {
                    r -= 1;
                    map.erase(R[r]);
                } else {
                    break;
                }
            }
            map[R[l]] = L[l];
            parent[0][l] = r;
        }
    }
    for (int i = 0; i < 19; ++i) {
        parent[i + 1] = vector<int>(N + 1);
        for (int j = 0; j <= N; ++j) {
            parent[i + 1][j] = parent[i][parent[i][j]];
        }
    }
    int Q;
    std::cin >> Q;
    while (Q--) {
        int l, r;
        std::cin >> l >> r;
        l -= 1;
        int ans = 0;
        for (int i = 19; i >= 0; --i) {
            if (parent[i][l] < r) {
                ans += 1 << i;
                l = parent[i][l];
            }
        }
        ans += 1;
        std::cout << ans << '\n';
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50