Submission #1129847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129847		crafticat	Escape Route 2 (JOI24_escape2)	C++17	14 / 100	227 ms	31240 KiB

Main

#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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

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

constexpr ll INF = 1e18;
using tup = tuple<ll, ll, ll>;

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;
}

ll T;

V<pair<pi, ll>> create(V<pi> x) {
    V<pair<pi, ll>> ans(x.size());
    for (ll i = 0; i < x.size(); ++i) {
        ans[i] = {x[i], 0};
    }
    return ans;
}

V<pair<pi, ll>> next(const V<pair<pi, ll>> &current, ll i, V<pi> &next, bool sign) {
    V<pair<pi, ll>> results;
    for (auto [dat, c] : current) {
        auto [a,b] = dat;
        auto it = std::lower_bound(next.begin(), next.end(), make_pair(b, -INF));
        if (it != next.end())
            results.emplace_back(make_pair(a, it->second), c);
        else if (!next.empty()){
            it = next.begin();
            results.emplace_back(make_pair(a, it->second), c + 1);
        }
    }
    return results;
}

int BLOCK;

ll findPar(ll l, ll r, int BSize) {
    ll mid = (r + l) / 2;
    ll best = mid;
    ll delta = (mid - l) / 2;

    FOR(t, l + delta + 1, mid + delta - 1) {
        if (in[t].size() < in[best].size()) best = t;
    }

    return best;
}

int GLOBALS = 0;

// Must jump over all l and r
void solve(ll l, ll r,const V<tuple<ll,ll,ll>> &queries) {
    ll mid = findPar(l, r, 1);
    if (r - l <= 1) {
        V<pair<pi, ll>> times = create(in[l]);

        for (auto [a,b, i] : queries) {
            ll res = INF;
            for (auto [dat, r] : times) {
                auto [x,y] = dat;
                res = min(res, y - x);
            }
            ans[i] = res;
        }
        return;
    }

    V<tuple<ll,ll,ll>> 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<pair<pi, ll>> times = create(in[mid]);
    V<V<pair<pi, ll>>> to, from;
    FOR(i, mid + 1, r) {
        to.emplace_back(times);
        times = next(times,i, in[i], false);
    }
    to.emplace_back(times);
    GLOBALS += in[mid].size() * (r - l);
    if (GLOBALS > 1e5) {
        exit(5);
    }

    times = create(out[mid]);
    for (auto &[aData,r] : times) {
        auto &[a,b] = aData;
        a = -b;
    }

    for (ll i = mid - 1; i >= l;i--) {
        from.emplace_back(times);
        times = next(times, i, out[i], true);
    }
    from.emplace_back(times);
    map<pi, ll> comp;

    for (auto [a,b, i] : currentQueries) {
        if (comp[{a,b}]) {
            ans[i] = comp[{a,b}];
            continue;
        }
        V<pair<pi, ll>> end = to[b - mid - 1];
        V<pair<pi, ll>> start = from[mid - a];

        ll bestTime = INF;
        for (auto [dat,c] : start) {
            auto [x,y] = dat;
            swap(x,y);
            x *= -1;

            auto it = std::lower_bound(end.begin(), end.end(), make_pair(make_pair(y, -INF), -INF));
            auto [dat2, c2] = *it;
            auto [x2,y2] = dat2;
            if (y <= x2) bestTime = min(bestTime, y2 - x + (c + c2) * T);
        }

        comp[{a,b}] = ans[i] = bestTime;
    }
}

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

    ll n; cin >> n >> T;
    in.resize(n), out.resize(n);
    BLOCK = 300;

    F0R(i, n - 1) {
        ll m; cin >> m;
        F0R(j, m) {
            ll a, b; cin >> a >> b;
            in[i].emplace_back(a,b);
        }
        sort(all(in[i]));
        in[i] = fix(in[i]);
        for (auto [a,b] : in[i]) {
            out[i].emplace_back(b,a);
        }

        F0R(j, out[i].size()) {
            out[i][j].f *= -1; // Switch signs
            out[i][j].s *= -1; // Switch signs
        }
        sort(all(out[i]));

    }

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

    F0R(i, q) {
        ll 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: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 17
• Subtask 4: 0 / 23
• Subtask 5: 0 / 36
• Subtask 6: 0 / 10