oj.uz

Submission #888946

# Submission time Handle Problem Language Result Execution time Memory
888946 2023-12-18T12:54:54 Z Alihan_8 Passport (JOI23_passport) C++17
48 / 100
 2000 ms 364308 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 <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 6492 KB Output is correct
3 Correct 2 ms 6540 KB Output is correct
4 Correct 272 ms 100816 KB Output is correct
5 Execution timed out 2037 ms 364308 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6724 KB Output is correct
5 Correct 2 ms 6492 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 6720 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 4 ms 7260 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 7520 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6724 KB Output is correct
5 Correct 2 ms 6492 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 6720 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 4 ms 7260 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 7520 KB Output is correct
16 Correct 4 ms 7772 KB Output is correct
17 Correct 138 ms 31064 KB Output is correct
18 Correct 4 ms 7768 KB Output is correct
19 Correct 4 ms 7780 KB Output is correct
20 Correct 1073 ms 203800 KB Output is correct
21 Correct 234 ms 56960 KB Output is correct
22 Correct 3 ms 7520 KB Output is correct
23 Correct 3 ms 7776 KB Output is correct
24 Correct 4 ms 7776 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6724 KB Output is correct
5 Correct 2 ms 6492 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 6720 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 4 ms 7260 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 7520 KB Output is correct
16 Correct 4 ms 7772 KB Output is correct
17 Correct 138 ms 31064 KB Output is correct
18 Correct 4 ms 7768 KB Output is correct
19 Correct 4 ms 7780 KB Output is correct
20 Correct 1073 ms 203800 KB Output is correct
21 Correct 234 ms 56960 KB Output is correct
22 Correct 3 ms 7520 KB Output is correct
23 Correct 3 ms 7776 KB Output is correct
24 Correct 4 ms 7776 KB Output is correct
25 Correct 2 ms 6500 KB Output is correct
26 Correct 2 ms 6628 KB Output is correct
27 Correct 4 ms 7776 KB Output is correct
28 Correct 120 ms 30976 KB Output is correct
29 Correct 1094 ms 203552 KB Output is correct
30 Correct 250 ms 56916 KB Output is correct
31 Correct 5 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 6492 KB Output is correct
3 Correct 2 ms 6540 KB Output is correct
4 Correct 272 ms 100816 KB Output is correct
5 Execution timed out 2037 ms 364308 KB Time limit exceeded
6 Halted 0 ms 0 KB -