Submission #1204153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204153		LucaIlie	Escape Route 2 (JOI24_escape2)	C++20	54 / 100	3074 ms	31080 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct range {
    int l, r;
};

const int MAX_N = 1e5;
const int MAX_LOG_N = 16;
const long long INF = 1e18;
int t;
vector<int> flightsByLoc[MAX_N + 1];
range flights[MAX_N + 1];
int nxt[MAX_LOG_N + 1][MAX_N + 1];
long long cost[MAX_LOG_N + 1][MAX_N + 1];

long long solve(int i, int k) {
    long long ans = -flights[i].l;
    for (int p = MAX_LOG_N; p >= 0; p--) {
        if (k >= (1 << p)) {
            k -= (1 << p);
            ans += (long long)t * cost[p][i];
            i = nxt[p][i];
        }
    }
    ans += flights[i].r;

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m = 0;
    
    cin >> n >> t;
    for (int i = 1; i <= n - 1; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int l, r;
            cin >> l >> r;
            flights[++m] = {l, r};
            flightsByLoc[i].push_back(m);
        }

        sort(flightsByLoc[i].begin(), flightsByLoc[i].end(), [](int a, int b) {
            return flights[a].l < flights[b].l;
        });
    }

    for (int i = 1; i <= n - 2; i++) {
        sort(flightsByLoc[i].begin(), flightsByLoc[i].end(), [](int a, int b) {
            return flights[a].r > flights[b].r;
        });

        int bestGlobalR = t, bestGlobalJ = 0;
        for (int j: flightsByLoc[i + 1]) {
            if (flights[j].r < bestGlobalR) {
                bestGlobalR = flights[j].r;
                bestGlobalJ = j;
            }
        }

        int ind = flightsByLoc[i + 1].size();
        int bestR = t, bestJ = 0;
        for (int j: flightsByLoc[i]) {
            while (ind > 0 && flights[flightsByLoc[i + 1][ind - 1]].l >= flights[j].r) {
                ind--;
                if (flights[flightsByLoc[i + 1][ind]].r < bestR) {
                    bestR = flights[flightsByLoc[i + 1][ind]].r;
                    bestJ = flightsByLoc[i + 1][ind];
                }
            }
            nxt[0][j] = (bestJ == 0 ? bestGlobalJ : bestJ);
        }

        sort(flightsByLoc[i].begin(), flightsByLoc[i].end(), [](int a, int b) {
            return flights[a].l < flights[b].l;
        });
    }
    
    for (int i = 1; i <= m; i++) {
        if (nxt[0][i] == 0)
            continue;
        cost[0][i] = (flights[i].r <= flights[nxt[0][i]].l ? 0 : 1);
    }

    // for (int i = 1; i <= m; i++)
        // printf("%d %d %lld\n", i, nxt[0][i], cost[0][i]);

    for (int p = 1; (1 << p) <= m; p++) {
        for (int i = 1; i <= m; i++) {
            nxt[p][i] = nxt[p - 1][nxt[p - 1][i]];
            cost[p][i] = cost[p - 1][i] + cost[p - 1][nxt[p - 1][i]];
        }
    }

    int q;
    cin >> q;
    for (; q > 0; q--) {
        int l, r;
        cin >> l >> r;

        int cnt = 0;
        long long best = INF;
        for (int j: flightsByLoc[l]) {
            best = min(best, solve(j, r - l - 1)); 
            if (cnt > 300)
                break;
            cnt++;
        }
        reverse(flightsByLoc[l].begin(), flightsByLoc[l].end());
        cnt = 0;
        for (int j: flightsByLoc[l]) {
            best = min(best, solve(j, r - l - 1)); 
            if (cnt > 300)
                break;
            cnt++;
        }

        cout << best << "\n";
    }

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 0 / 36
• Subtask 6: 0 / 10