oj.uz

Submission #888945

# Submission time Handle Problem Language Result Execution time Memory
888945 2023-12-18T12:53:14 Z Alihan_8 Passport (JOI23_passport) C++17
48 / 100
 2000 ms 311228 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int inf = 1e15 + 1;

struct Sparse{
    vector <vector<int>> T;
    vector <int> A;
    int _s;
    Sparse(auto &a, int s){
        int n = a.size();
        T.resize(20);
        _s = s; A = a;
        for ( auto &j: A ) j *= s;
        for ( auto &x: T ) x.resize(n);
        for ( int i = 0; i < n; i++ ){
            T[0][i] = i;
        }
        for ( int i = 1; i < 20; i++ ){
            int k = 1 << i - 1;
            for ( int j = 0; j < n; j++ ){
                if ( A[T[i - 1][j]] < A[T[i - 1][min(n - 1, j + k)]] ){
                    T[i][j] = T[i - 1][j];
                } else T[i][j] = T[i - 1][min(n - 1, j + k)];
            }
        }
    }
    int get(int l, int r){
        int lg = __lg(r - l + 1), k = 1 << lg;
        int u = T[lg][l], v = T[lg][r - k + 1];
        return A[u] < A[v] ? u : v;
    }
};

const int N = 2e5 + 1;

int S;

struct SegTree{
    int T[N * 4];
    SegTree(){
        for ( int i = 0; i < N * 4; i++ ){
            T[i] = inf;
        }
    }
    void upd(int v, int l, int r, int pos, int val){
        if ( l == r ){
            T[v] = val;
            return;
        }
        int md = (l + r) >> 1;
        if ( pos > md ){
            upd(v * 2 + 1, md + 1, r, pos, val);
        } else{
            upd(v * 2, l, md, pos, val);
        }
        T[v] = min(T[v * 2], T[v * 2 + 1]);
    };
    void upd(int pos, int val){
        upd(1, 0, S - 1, pos, val);
    }
    int get(int v, int l, int r, int tl, int tr){
        if ( l > tr or r < tl ){
            return inf;
        }
        if ( tl <= l && tr >= r ){
            return T[v];
        }
        int md = (l + r) >> 1;
        return min(get(v * 2, l, md, tl, tr), get(v * 2 + 1, md + 1, r, tl, tr));
    }
    int get(int l, int r){
        return get(1, 0, S - 1, l, r);
    }
} seg;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    S = n;
    vector <int> L(n), R(n);
    for ( int i = 0; i < n; i++ ){
        cin >> L[i] >> R[i];
        --L[i], --R[i];
    }
    Sparse mn(L, 1), mx(R, -1);
    vector <int> p(n);
    iota(all(p), 0);
    sort(all(p), [&](int &x, int &y){
         return R[x] - L[x] > R[y] - L[y];
    });
    vector <unordered_map<int,int>> dp(n);
    dp[0][n - 1] = 0;
    auto dfs = [&](auto dfs, int l, int r) -> int{
        if ( dp[l].count(r) ){
            return dp[l][r];
        }
        int ret = inf, L_ = mn.get(l, r), R_ = mx.get(l, r);
        if ( R[R_] > r ){
            chmin(ret, dfs(dfs, min(L[R_], l), R[R_]) + 1);
        }
        if ( L[L_] < l ){
            chmin(ret, dfs(dfs, L[L_], max(r, R[L_])) + 1);
        }
        return dp[l][r] = min(seg.get(l, r), ret);
    };
    vector <int> ans(n);
    for ( auto &i: p ){
        ans[i] = dfs(dfs, L[i], R[i]) + 1;
        seg.upd(i, ans[i]);
    }
    int q; cin >> q;
    while ( q-- ){
        int x; cin >> x;
        --x;
        cout << (ans[x] >= inf ? -1 : ans[x]) << ln;
    }

    cout << '\n';
}

Compilation message

passport.cpp:37:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   37 |     Sparse(auto &a, int s){
      |            ^~~~
passport.cpp: In instantiation of 'Sparse::Sparse(auto:23&, long long int) [with auto:23 = std::vector<long long int>]':
passport.cpp:115:19:   required from here
passport.cpp:47:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   47 |             int k = 1 << i - 1;
      |                          ~~^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 274 ms 107076 KB Output is correct
5 Execution timed out 2072 ms 311228 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6744 KB Output is correct
12 Correct 4 ms 7000 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 4 ms 7512 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6744 KB Output is correct
12 Correct 4 ms 7000 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 4 ms 7512 KB Output is correct
16 Correct 4 ms 7772 KB Output is correct
17 Correct 98 ms 23856 KB Output is correct
18 Correct 4 ms 7772 KB Output is correct
19 Correct 4 ms 7772 KB Output is correct
20 Correct 726 ms 140984 KB Output is correct
21 Correct 158 ms 41552 KB Output is correct
22 Correct 3 ms 7768 KB Output is correct
23 Correct 3 ms 7888 KB Output is correct
24 Correct 4 ms 8028 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6744 KB Output is correct
12 Correct 4 ms 7000 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 4 ms 7512 KB Output is correct
16 Correct 4 ms 7772 KB Output is correct
17 Correct 98 ms 23856 KB Output is correct
18 Correct 4 ms 7772 KB Output is correct
19 Correct 4 ms 7772 KB Output is correct
20 Correct 726 ms 140984 KB Output is correct
21 Correct 158 ms 41552 KB Output is correct
22 Correct 3 ms 7768 KB Output is correct
23 Correct 3 ms 7888 KB Output is correct
24 Correct 4 ms 8028 KB Output is correct
25 Correct 2 ms 6492 KB Output is correct
26 Correct 2 ms 6492 KB Output is correct
27 Correct 4 ms 7772 KB Output is correct
28 Correct 99 ms 23796 KB Output is correct
29 Correct 726 ms 141140 KB Output is correct
30 Correct 155 ms 41656 KB Output is correct
31 Correct 4 ms 7768 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 274 ms 107076 KB Output is correct
5 Execution timed out 2072 ms 311228 KB Time limit exceeded
6 Halted 0 ms 0 KB -