Submission #986624

#	Time	Username	Problem	Language	Result	Execution time	Memory
986624		876pol	Passport (JOI23_passport)	C++17	100 / 100	806 ms	32860 KiB

passport

#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define dbg(...)
#define STRUCT_DBG(...)
#else
#include "lib/debug.h"
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
using vll = vector<ll>;
using vpll = vector<pair<ll, ll>>;
using vvll = vector<vector<ll>>;
using vvpll = vector<vector<pair<ll, ll>>>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define RFOR(i, e, s) for (ll i = (ll)e - 1; i >= (ll)s; i--)
#define TRAV(a, c) for (const auto &a : c)
#define all(x) x.begin(), x.end()

#define MOD 1000000007
// #define MOD 998244353

#define FASTIO
#define PRECISION
// #define FILE "file"

#define SINGLE
// #define MULTIPLE
// #define GOOGLE

void solve() {
    ll n;
    cin >> n;
    vpll a(n + 1);
    CFOR(i, 1, n) cin >> a[i].first >> a[i].second;
    auto cal = [&](vll &dist, vll &fr) {
        vvpll ranges(n + 1);
        CFOR(i, 2, n) ranges[a[i].first].push_back({a[i].second, i});
        CFOR(i, 1, n) sort(all(ranges[i]));
        vpll seg(2 * n, {-1, -1});
#define lc(v) (v + 1)
#define rc(v) (v + 2 * (tm - tl + 1))
        function<void(ll, ll, ll)> build = [&](ll v, ll tl, ll tr) {
            if (tl == tr) {
                if (ranges[tl].size()) {
                    seg[v] = ranges[tl].back();
                    ranges[tl].pop_back();
                }
            } else {
                ll tm = (tl + tr) / 2;
                build(lc(v), tl, tm);
                build(rc(v), tm + 1, tr);
                seg[v] = max(seg[lc(v)], seg[rc(v)]);
            }
        };
        build(0, 1, n);
        function<pll(ll, ll, ll, ll)> query = [&](ll v, ll tl, ll tr,
                                                  ll ind) -> pll {
            if (tr <= ind) return seg[v];
            if (ind < tl) return {-1, -1};
            ll tm = (tl + tr) / 2;
            return max(query(lc(v), tl, tm, ind),
                       query(rc(v), tm + 1, tr, ind));
        };
        function<void(ll, ll, ll, ll)> erase = [&](ll v, ll tl, ll tr, ll ind) {
            if (tl == tr && tl == ind) {
                if (ranges[ind].size()) {
                    seg[v] = ranges[ind].back();
                    ranges[ind].pop_back();
                } else {
                    seg[v] = {-1, -1};
                }
            } else {
                ll tm = (tl + tr) / 2;
                if (ind <= tm) {
                    erase(lc(v), tl, tm, ind);
                } else {
                    erase(rc(v), tm + 1, tr, ind);
                }
                seg[v] = max(seg[lc(v)], seg[rc(v)]);
            }
        };
        deque<pll> qu = {{1, 1}};  // index, fr
        ll cdist = 0;
        while (qu.size()) {
            for (ll _ = 0, t = qu.size(); _ < t; _++) {
                auto node = qu.front();
                qu.pop_front();
                dist[node.first] = cdist;
                fr[node.first] = node.second;
                pll obj;
                while ((obj = query(0, 1, n, node.first)) != pll{-1, -1} &&
                       node.first <= obj.first) {
                    qu.push_back({obj.second, max(node.second, obj.first)});
                    erase(0, 1, n, a[obj.second].first);
                }
            }
            cdist++;
            sort(all(qu), [&](const pll &o1, const pll &o2) {
                return o1.second > o2.second;
            });
        }
    };

    vll t1(n + 1, INT_MAX), fr1(n + 1), t2(n + 1, INT_MAX), fr2(n + 1);
    cal(t1, fr1);
    reverse(a.begin() + 1, a.end());
    CFOR(i, 1, n) {
        a[i].first = n - a[i].first + 1;
        a[i].second = n - a[i].second + 1;
        swap(a[i].first, a[i].second);
    }
    cal(t2, fr2);
    reverse(t2.begin() + 1, t2.end());
    reverse(fr2.begin() + 1, fr2.end());
    CFOR(i, 1, n) if (fr2[i]) fr2[i] = n - fr2[i] + 1;
    vll mxt1(t1), mxt2(t2);
    RFOR(i, n, 1) mxt1[i] = min(mxt1[i], mxt1[i + 1]);
    CFOR(i, 2, n) mxt2[i] = min(mxt2[i], mxt2[i - 1]);
    // dbg(t1, fr1, t2, fr2, mxt1, mxt2);
    ll q;
    cin >> q;
    FOR(i, 0, q) {
        ll x;
        cin >> x;
        ll ans = min(t1[x] + mxt2[fr1[x]], t2[x] + mxt1[fr2[x]]);
        cout << (ans >= INT_MAX ? -1 : ans) << "\n";
        // cout << (t1[x] + t2[fr1[x]] >= INT_MAX ? -1 : t1[x] + t2[fr1[x]])
        //      << "\n";
    }
}

int main() {
#ifdef FASTIO
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#endif
#ifdef PRECISION
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
#endif
#ifdef FILE
    freopen((FILE + string(".in")).c_str(), "r", stdin);
    freopen((FILE + string(".out")).c_str(), "w", stdout);
#endif
#ifdef SINGLE
    solve();
#endif
#ifdef MULTIPLE
    ll t;
    cin >> t;
    for (ll i = 1; i <= t; i++) {
        solve();
    }
#endif
#ifdef GOOGLE
    ll t;
    cin >> t;
    for (ll i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        solve();
    }
#endif
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46