제출 #1204158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204158		LucaIlie	Escape Route 2 (JOI24_escape2)	C++20	54 / 100	3096 ms	31148 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].r;
    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].l;

    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].r > flights[b].r;
        });

    }

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

        int bestGlobalL = -1, bestGlobalJ = 0;
        for (int j: flightsByLoc[i - 1]) {
            if (flights[j].l > bestGlobalL) {
                bestGlobalL = flights[j].l;
                bestGlobalJ = j;
            }
        }

        int ind = flightsByLoc[i - 1].size();
        int bestL = -1, bestJ = 0;
        for (int j: flightsByLoc[i]) {
            while (ind > 0 && flights[flightsByLoc[i - 1][ind - 1]].r <= flights[j].l) {
                ind--;
                if (flights[flightsByLoc[i - 1][ind]].l > bestL) {
                    bestL = flights[flightsByLoc[i - 1][ind]].l;
                    bestJ = flightsByLoc[i - 1][ind];
                }
            }
            int l = (bestJ == 0 ? bestGlobalJ : bestJ);
            nxt[0][j] = l;
        }
    }
    
    for (int i = 1; i <= m; i++) {
        if (nxt[0][i] == 0)
            continue;
        cost[0][i] = (flights[i].l >= flights[nxt[0][i]].r ? 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[r - 1]) {
            best = min(best, solve(j, r - l - 1)); 
            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