Submission #1117230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117230		_callmelucian	Escape Route 2 (JOI24_escape2)	C++14	54 / 100	3043 ms	132424 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5, Q = 3e5 + 5;
vector<pl> nxt[18][mn], flight[mn], qry[mn];
vector<int> ord[mn];
ll ans[Q], n, T;

ll travel (int node, int flightID, int step) {
    ll ans = 0;
    for (int i = 0; step; step >>= 1, i++) {
        if ((step & 1) == 0) continue;
        ll weight; tie(flightID, weight) = nxt[i][node][flightID];
        ans += weight, node += (1 << i);
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    // read flights info
    cin >> n >> T;
    for (int i = 1; i < n; i++) {
        int m; cin >> m;
        flight[i].resize(m);
        for (int j = 0; j < m; j++) {
            int a, b; cin >> a >> b;
            flight[i][j] = {a, b};
        }
        sort(all(flight[i]));
    }

    // resize + setup stuffs
    for (int i = 1; i < n; i++) {
        ord[i].resize(flight[i].size());
        for (int s = 0; s < 18; s++)
            nxt[s][i].resize(flight[i].size());
        for (int j = 0; j < ord[i].size(); j++) ord[i][j] = j;
        sort(all(ord[i]), [&] (int a, int b)
            { return flight[i][a].second > flight[i][b].second; });
    }

    // build edge
    for (int i = 1; i + 1 < n; i++) {
        int iter = flight[i + 1].size(), best = INT_MAX, idx = -1;
        int soonest = min_element(all(flight[i + 1]), [&] (pii a, pii b) { return a.second < b.second; } ) - flight[i + 1].begin();
        for (int u : ord[i]) {
            // calculate transition for nxt[i][u]
            while (iter - 1 >= 0 && flight[i][u].second <= flight[i + 1][iter - 1].first) {
                int cur = flight[i + 1][--iter].second;
                if (cur < best) best = cur, idx = iter;
            }
            if (idx == -1) { // wait overnight and take the `soonest` flight
//                cout << "state " << i << " " << u << "\n";
                ll link = soonest, weight = T - flight[i][u].second + flight[i + 1][soonest].second;
                nxt[0][i][u] = {link, weight};
            }
            else { // take the `best` flight to fly in the same day
                ll link = idx, weight = flight[i + 1][idx].second - flight[i][u].second;
                nxt[0][i][u] = {link, weight};
            }

            int link, weight; tie(link, weight) = nxt[0][i][u];
//            cout << "(" << i << ", " << u << ") -> (" << i + 1 << ", " << link << "), weight " << weight << "\n";
        }
    }

    // binary-lifting pre-processing
    for (int s = 1; s < 18; s++) {
        for (int i = 1; i + (1 << s) < n; i++) {
            for (int j = 0; j < flight[i].size(); j++) {
                ll link, weight; tie(link, weight) = nxt[s - 1][i][j];
                ll nxtLink, nxtWeight; tie(nxtLink, nxtWeight) = nxt[s - 1][i + (1 << (s - 1))][link];
                nxt[s][i][j] = {nxtLink, weight + nxtWeight};
            }
        }
    }

    // read queries
    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        qry[l].emplace_back(r, i);
    }

    // process queries
    for (int i = 1; i < n; i++) {
        if (qry[i].empty()) continue;
        sort(all(qry[i]));

        function<ll(int,int)> tryFlight = [&] (int flightID, int destination) {
            int step = destination - i - 1;
            return travel(i, flightID, step) + flight[i][flightID].second - flight[i][flightID].first;
        };

        for (auto [r, idx] : qry[i]) {
            ans[idx] = LLONG_MAX;
            for (int u : ord[i]) ans[idx] = min(ans[idx], tryFlight(u, r));
        }

//        function<void(int,int,int,int)> solve = [&] (int a, int b, int optL, int optR) {
//            if (i == 2) {
//                cout << "solve {";
//                for (int jj = a; jj <= b; jj++) cout << qry[i][jj].second << " ";
//                cout << "}, ";
//                cout << optL << ".." << optR << "\n";
//            }
//
//            if (optL == optR) {
//                for (int it = a; it <= b; it++) {
//                    int r, idx; tie(r, idx) = qry[i][it];
//                    ans[idx] = tryFlight(ord[i][optL], r);
//                }
//                return;
//            }
//            int mid = (a + b) >> 1, bestID = -1;
//            ll best = LLONG_MAX;
//
//            int r, idx; tie(r, idx) = qry[i][mid];
//            for (int tryID = optL; tryID <= optR; tryID++) {
//                if (i == 2 && idx == 2) {
//                    cout << "wth " << ord[i][tryID] << " " << tryFlight(ord[i][tryID], r) << "\n";
//                    cout << "bruh " << i << " " << r << " " << travel(i, ord[i][tryID], r - i - 1) << "\n";
//                }
//                ll cur = tryFlight(ord[i][tryID], r);
//                if (cur < best) best = cur, bestID = tryID;
//            }
//            ans[idx] = best;
//            if (a < mid) solve(a, mid - 1, optL, bestID);
//            if (mid < b) solve(mid + 1, b, bestID, optR);
//        };
//        solve(0, qry[i].size() - 1, 0, ord[i].size() - 1);

//        for (pii item : qry[i]) {
//            int r, idx; tie(r, idx) = item;
//
//            res = (iter == -1 ? LLONG_MAX : travel(i, ord[i][iter], r - i - 1) + flight[i][ord[i][iter]].second - flight[i][ord[i][iter]].first);
//            while (iter + 1 < ord[i].size()) {
//                int u = ord[i][iter + 1];
//                ll tryFinish = travel(i, u, r - i - 1) + flight[i][u].second - flight[i][u].first;
//                if (i == 3) cout << "bruh " << idx << " " << travel(i, u, r - i - 1) << " " << r - i - 1 << " " << u << "\n";
//                if (tryFinish < res) res = tryFinish, iter++;
//                else break;
////                cout << "jump " << i << " " << u << " " << r - i - 1 << "-step " << res << "\n";
//            }
//            ans[idx] = res;
//        }
    }

    // print output
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int j = 0; j < ord[i].size(); j++) ord[i][j] = j;
      |                         ~~^~~~~~~~~~~~~~~
Main.cpp:83:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for (int j = 0; j < flight[i].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~
Main.cpp:108:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |         for (auto [r, idx] : qry[i]) {
      |                   ^

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