Submission #1129755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129755		crafticat	Escape Route 2 (JOI24_escape2)	C++20	0 / 100	0 ms	324 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define F0R(i, n) for (int i = 0; i < n;i++)
#define FOR(i,j,n) for(int i = j;i < n;i++)
template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;

#define all(x) x.begin(), x.end()
#define f first
#define s second

constexpr int INF = 1e9;

vi ans;
V<V<pi>> in, out;

V<pi> fix(V<pi> arr) {
    V<pi> fixed;
    F0R(i, arr.size()) {
        while (!fixed.empty() and fixed.back().s > arr[i].s) fixed.pop_back();
        fixed.push_back(arr[i]);
    }
    return fixed;
}

int T;

int sign(int x) {
    if (x >= 0) return 1;
    return -1;
}

V<pi> next(const V<pi> &current, int i, V<pi> &in) {
    V<pi> results;
    for (auto [a, b] : current) {
        auto it = std::lower_bound(in.begin(), in.end(), make_pair(b % T,-INF));
        if (it != in.end())
            results.emplace_back(a, it->second);
        else if (!in.empty()){
            it = in.begin();
            results.emplace_back(a, it->second + T);
        }
    }
    return results;
}

// Must jump over all l and r
void solve(int l, int r, V<tuple<int,int,int>> queries) {
    int mid = (r + l) / 2;
    if (r - l <= 1) return;

    V<tuple<int,int,int>> leftQueries, rightQueries, currentQueries;
    for (auto [a, b, i] : queries) {
        if (b <= mid) leftQueries.emplace_back(a,b,i);
        else if (a >= mid) rightQueries.emplace_back(a, b, i);
        else currentQueries.emplace_back(a, b, i);
    }

    solve(l, mid, leftQueries);
    solve(mid, r, rightQueries);

    V<pi> times = in[mid];
    V<V<pi>> to, from;
    FOR(i, mid + 1, r) {
        to.emplace_back(times);
        times = next(times,i, in[i]);
    }
    to.emplace_back(times);

    times = out[mid];
    for (auto &[a,b] : times) a = -b;

    for (int i = mid - 1; i >= l;i--) {
        from.emplace_back(times);
        times = next(times, i, out[i]);
    }
    from.emplace_back(times);

    map<int, int> inId, outId;
    int iter = 0;
    for (auto [a,b] : in[mid]) {
        inId[a] = iter++;
    }
    iter = 0;
    for (auto [b, a] : out[mid]) {
        outId[b] = iter++;
    }

    for (auto [a,b, i] : currentQueries) {
        V<pi> end = to[b - mid - 1];
        V<pi> start = from[mid - a];

        int bestTime = 1e9;
        for (auto [x,y] : start) {
            swap(x,y);
            x *= -1;

            for (auto [x2, y2] : end) {
                if (y <= x2) bestTime = min(bestTime, y2 - x);
            }
        }

        ans[i] = bestTime;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n; cin >> n >> T;
    in.resize(n), out.resize(n);

    F0R(i, n - 1) {
        int m; cin >> m;
        F0R(j, m) {
            int a, b; cin >> a >> b;
            in[i].emplace_back(a,b);
            out[i].emplace_back(b, a);
        }
        sort(all(in[i]));
        sort(all(out[i]));
        out[i] = fix(out[i]);
        F0R(j, m) out[i][j].f *= -1; // Switch signs
        F0R(j, m) out[i][j].s *= -1; // Switch signs
        sort(all(out[i]));

        in[i] = fix(in[i]);
    }

    V<tuple<int,int,int>> queries;
    int q; cin >> q;
    ans.resize(q);

    F0R(i, q) {
        int l, r; cin >> l >> r;
        l--;
        r--;
        queries.emplace_back(l, r, i);
    }

    solve(0, n, queries);
    F0R(i, q) {
        cout << ans[i] << "\n";
    }

    return 0;
}

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