Submission #1204173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204173		LucaIlie	Escape Route 2 (JOI24_escape2)	C++20	100 / 100	1110 ms	51092 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 int LIM = 1000;
const long long INF = 1e18;
int t;
vector<int> flightsByLoc[MAX_N + 1];
range flights[MAX_N + 1];
int prv[MAX_LOG_N + 1][MAX_N + 1];
int nxt[MAX_N + 1];
int costPrv[MAX_LOG_N + 1][MAX_N + 1];
int costNxt[MAX_N + 1];
long long dist[MAX_N + 1];
unordered_map<int, long long> answer[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 * costPrv[p][i];
            i = prv[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);
            prv[0][j] = l;
        }
    }
    
    for (int i = 1; i <= m; i++) {
        if (prv[0][i] == 0)
            continue;
        costPrv[0][i] = (flights[i].l >= flights[prv[0][i]].r ? 0 : 1);
    }
    for (int p = 1; (1 << p) <= m; p++) {
        for (int i = 1; i <= m; i++) {
            prv[p][i] = prv[p - 1][prv[p - 1][i]];
            costPrv[p][i] = costPrv[p - 1][i] + costPrv[p - 1][prv[p - 1][i]];
        }
    }

    
    for (int i = 1; i <= n - 1; i++) {
        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[j] = (bestJ == 0 ? bestGlobalJ : bestJ);
        }
    }
    for (int i = 1; i <= m; i++) {
        if (nxt[i] == 0)
            continue;
        costNxt[i] = (flights[i].r <= flights[nxt[i]].l ? 0 : 1);
    }
    
     // for (int i = 1; i <= m; i++)
         // printf("%d %d %d\n", i, nxt[i], costNxt[i]);

    for (int r = 2; r <= n; r++) {
        if ((int)flightsByLoc[r - 1].size() < LIM)
            continue;
            
        answer[r - 1][r] = INF;
        for (int i: flightsByLoc[r - 1]) {
            dist[i] = flights[i].r;
            answer[r - 1][r] = min(answer[r - 1][r], dist[i] - flights[i].l);
        }

        for (int l = r - 2; l >= 1; l--) {
            answer[l][r] = INF;
            for (int i: flightsByLoc[l]) {
                dist[i] = dist[nxt[i]] + (long long)t * costNxt[i];
                answer[l][r] = min(answer[l][r], dist[i] - flights[i].l);
            }
        }
    }

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

        if (answer[l][r]) {
            cout << answer[l][r] << "\n";
            continue;
        }

        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: 36 / 36
• Subtask 6: 10 / 10