Submission #1117375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117375		_callmelucian	Escape Route 2 (JOI24_escape2)	C++14	100 / 100	592 ms	129392 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;
//const int limFlight = 10, limQuery = 10;
const int limFlight = 316, limQuery = 1000;

vector<pl> flight[mn], nxt[18][mn], qry[mn];
vector<ll> save[mn];
ll best[mn], ans[Q], n, T;

void refine (vector<pl> &vec) {
    priority_queue<pl> pq;
    sort(all(vec), [&] (pl a, pl b)
         { return (a.first == b.first ? a.second > b.second : a.first < b.first); });

    for (pl item : vec) {
        ll a, b; tie(a, b) = item;
        while (pq.size() && pq.top().first >= b) pq.pop();
        pq.emplace(b, a);
    }
    vec.clear();

    while (pq.size()) {
        ll a, b; tie(b, a) = pq.top(); pq.pop();
        vec.emplace_back(a, b);
    }
    reverse(all(vec));
}

ll quickJump (int u, 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][u][flightID];
        u += (1 << i), ans += weight;
    }
    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 (pl &it : flight[i])
            cin >> it.first >> it.second;
        refine(flight[i]);
        assert(flight[i].size());
    }

    for (int s = 0; s < 18; s++)
        for (int i = 1; i < n; i++) nxt[s][i].resize(flight[i].size());

    /// construct edges + bin-lift pre-compute
    for (int i = 1; i + 1 < n; i++) {
        int iter = 0;
        for (int j = 0; j < flight[i].size(); j++) {
            while (iter < flight[i + 1].size() && flight[i][j].second > flight[i + 1][iter].first) iter++;
            if (iter < flight[i + 1].size())
                nxt[0][i][j] = {iter, flight[i + 1][iter].second - flight[i][j].second};
            else nxt[0][i][j] = {0, flight[i + 1][0].second + T - flight[i][j].second};

//            cout << "(" << i << ", " << j << ") -> (" << i + 1 << ", " << nxt[0][i][j].first << "), weight " << nxt[0][i][j].second << "\n";
        }
    }
    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 id, weight; tie(id, weight) = nxt[s - 1][i][j];
                ll nxtID, nxtWeight; tie(nxtID, nxtWeight) = nxt[s - 1][i + (1 << (s - 1))][id];
                nxt[s][i][j] = {nxtID, 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;
        if (flight[i].size() > limFlight || qry[i].size() > limQuery) { // calculate for every possible R
            for (int j = i; j < n; j++) save[j] = vector<ll>(flight[j].size(), LLONG_MAX);
            for (int k = 0; k < flight[i].size(); k++)
                save[i][k] = flight[i][k].second - flight[i][k].first;
            for (int j = i; j + 1 < n; j++) {
                for (int k = 0; k < flight[j].size(); k++) {
                    if (save[j][k] == LLONG_MAX) continue;
                    ll nxtID, weight; tie(nxtID, weight) = nxt[0][j][k];
                    save[j + 1][nxtID] = min(save[j + 1][nxtID], save[j][k] + weight);
                }
            }
            for (int j = i; j < n; j++) best[j] = *min_element(all(save[j]));
            for (pii item : qry[i]) {
                int r, idx; tie(r, idx) = item;
                ans[idx] = best[r - 1];
            }
        }
        else { // simply brute-force
            for (pii item : qry[i]) {
                int r, idx; tie(r, idx) = item;
                ans[idx] = LLONG_MAX;
                for (int k = 0; k < flight[i].size(); k++)
                    ans[idx] = min(ans[idx], quickJump(i, k, r - i - 1) + flight[i][k].second - flight[i][k].first);
            }
        }
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:72:27: 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]
   72 |         for (int j = 0; j < flight[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~
Main.cpp:73:25: 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]
   73 |             while (iter < flight[i + 1].size() && flight[i][j].second > flight[i + 1][iter].first) iter++;
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:74:22: 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]
   74 |             if (iter < flight[i + 1].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
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:103: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]
  103 |             for (int k = 0; k < flight[i].size(); k++)
      |                             ~~^~~~~~~~~~~~~~~~~~
Main.cpp:106:35: 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]
  106 |                 for (int k = 0; k < flight[j].size(); k++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~
Main.cpp:122:35: 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]
  122 |                 for (int k = 0; k < flight[i].size(); k++)
      |                                 ~~^~~~~~~~~~~~~~~~~~

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