Submission #986524

#	Time	Username	Problem	Language	Result	Execution time	Memory
986524		876pol	Passport (JOI23_passport)	C++17	16 / 100	2080 ms	13624 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

struct pass {
    ll l, r, i;
};

STRUCT_DBG(pass, false, &pass::l, &pass::r, &pass::i);

void solve() {
    ll n;
    cin >> n;
    vec<pass> a(n);
    FOR(i, 0, n) {
        cin >> a[i].l >> a[i].r;
        a[i].i = i + 1;
    }
    sort(all(a), [&](const pass &o1, const pass &o2) { return o1.l < o2.l; });
    vpll seg(2 * n, {INT_MAX, INT_MAX});
#define lc(v) (v + 1)
#define rc(v) (v + 2 * (tm - tl + 1))
    function<void(ll, ll, ll, ll, pll)> update = [&](ll v, ll tl, ll tr, ll ind,
                                                     pll x) {
        if (tl == tr && tl == ind) {
            seg[v] = x;
        } else {
            ll tm = (tl + tr) / 2;
            if (ind <= tm) {
                update(lc(v), tl, tm, ind, x);
            } else {
                update(rc(v), tm + 1, tr, ind, x);
            }
            seg[v] = min(seg[lc(v)], seg[rc(v)]);
        }
    };
    function<pll(ll, ll, ll, ll, ll)> query = [&](ll v, ll tl, ll tr, ll l,
                                                  ll r) -> pll {
        if (r < tl || tr < l) return {INT_MAX, INT_MAX};
        if (l <= tl && tr <= r) return seg[v];
        ll tm = (tl + tr) / 2;
        return min(query(lc(v), tl, tm, l, r), query(rc(v), tm + 1, tr, l, r));
    };
    update(0, 1, n, 1, {0, -1});
    FOR(i, 0, n) {
        TRAV(e, a) {
            if (e.i == 1) continue;
            pll obj = query(0, 1, n, e.l, e.r);
            update(0, 1, n, e.i, {obj.first + 1, min(obj.second, -e.r)});
        }
    }
    vll t1(n + 1), fr1(n + 1);
    CFOR(i, 1, n) t1[i] = query(0, 1, n, i, i).first;
    CFOR(i, 1, n) fr1[i] = query(0, 1, n, i, i).second;
    fill(all(seg), pll{INT_MAX, INT_MAX});

    update(0, 1, n, n, {0, 0});
    FOR(i, 0, n) {
        TRAV(e, a) {
            if (e.i == n) continue;
            pll obj = query(0, 1, n, e.l, e.r);
            update(0, 1, n, e.i, {obj.first + 1, 0});
        }
    }
    vll t2(n + 1);
    CFOR(i, 1, n) t2[i] = query(0, 1, n, i, i).first;
    vll ans(n + 1, INT_MAX);
    CFOR(i, 1, n) {
        CFOR(j, 1, -fr1[i]) {
            ans[i] = min(ans[i], t1[i] + t2[j]);
        }
    }
    ll q;
    cin >> q;
    FOR(i, 0, q) {
        ll x;
        cin >> x;
        cout << (ans[x] == INT_MAX ? -1 : ans[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: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46