Submission #986558

#	Time	Username	Problem	Language	Result	Execution time	Memory
986558		876pol	Passport (JOI23_passport)	C++17	0 / 100	566 ms	1048576 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;
    vvll dp(n + 1, vll(n + 1, INT_MAX)), mx(n + 1, vll(n + 1, -1));
    CFOR(i, 1, n) {
        CFOR(j, i, n) {
            mx[i][j] = max(mx[i][j - 1], a[j].second);
        }
    }
    dp[1][n] = 0;
    RFOR(i, n, 1) {
        if (mx[1][i] == -1) continue;
        dp[1][i] = min(dp[1][i], dp[1][mx[1][i]] + 1);
    }
    CFOR(i, 2, n) {
        CFOR(j, i, n) {
            dp[i][j] =
                min(dp[i][j], dp[min(i, a[j].first)][max(j, a[j].second)] + 1);
            if (i < j) dp[i][j] = min(dp[i][j - 1], dp[i][j]);
        }
        RFOR(j, n, 1) {
            if (mx[i][j] == -1) continue;
            dp[i][j] = min(dp[i][j], dp[i][mx[i][j]] + 1);
        }
    }
    ll q;
    cin >> q;
    FOR(i, 0, q) {
        ll x;
        cin >> x;
        cout << (dp[x][x] == INT_MAX ? -1 : dp[x][x]) << "\n";
    }

    //     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: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46