oj.uz

Submission #986524

# Submission time Handle Problem Language Result Execution time Memory
986524 2024-05-20T17:44:49 Z 876pol Passport (JOI23_passport) C++17
16 / 100
 2000 ms 13624 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 2080 ms 13624 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 76 ms 472 KB Output is correct
12 Correct 66 ms 452 KB Output is correct
13 Correct 82 ms 348 KB Output is correct
14 Correct 72 ms 348 KB Output is correct
15 Correct 65 ms 348 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 76 ms 472 KB Output is correct
12 Correct 66 ms 452 KB Output is correct
13 Correct 82 ms 348 KB Output is correct
14 Correct 72 ms 348 KB Output is correct
15 Correct 65 ms 348 KB Output is correct
16 Execution timed out 2066 ms 604 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 76 ms 472 KB Output is correct
12 Correct 66 ms 452 KB Output is correct
13 Correct 82 ms 348 KB Output is correct
14 Correct 72 ms 348 KB Output is correct
15 Correct 65 ms 348 KB Output is correct
16 Execution timed out 2066 ms 604 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 2080 ms 13624 KB Time limit exceeded
5 Halted 0 ms 0 KB -