oj.uz

Submission #986618

# Submission time Handle Problem Language Result Execution time Memory
986618 2024-05-20T23:24:45 Z 876pol Passport (JOI23_passport) C++17
6 / 100
 759 ms 30748 KB 
#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());
    CFOR(i, 1, n) t2[i] = min(t2[i], t2[i - 1]);
    ll q;
    cin >> q;
    FOR(i, 0, q) {
        ll x;
        cin >> x;
        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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 759 ms 30748 KB Output is correct
5 Correct 575 ms 28504 KB Output is correct
6 Correct 573 ms 29640 KB Output is correct
7 Correct 582 ms 28952 KB Output is correct
8 Correct 257 ms 22320 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 759 ms 30748 KB Output is correct
5 Correct 575 ms 28504 KB Output is correct
6 Correct 573 ms 29640 KB Output is correct
7 Correct 582 ms 28952 KB Output is correct
8 Correct 257 ms 22320 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -