oj.uz

Submission #784143

# Submission time Handle Problem Language Result Execution time Memory
784143 2023-07-15T18:41:40 Z RushB Passport (JOI23_passport) C++17
6 / 100
 182 ms 86620 KB 
#include <bits/stdc++.h>
using namespace std;
using ar = array<int, 2>;
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 
const int64_t INF = 1 << 30;
const int N = 2e5 + 5;
const int L = 19;
ar mxR[N][L], mnL[N][L];
array<int, 2> a[N];
vector<int> adj[N];
int lft[N], rht[N], dist[N], n;
bitset<N> isL, isR;

int maxR(int l, int r) {
        int t = __lg(r - l + 1);
        return max(mxR[l][t], mxR[r - (1 << t) + 1][t])[1];
}
int minL(int l, int r) {
        int t = __lg(r - l + 1);
        return min(mnL[l][t], mnL[r - (1 << t) + 1][t])[1];
}

signed main() {
        ios::sync_with_stdio(0), cin.tie(0);
        cin >> n;
        FOR(i, 0, n) {
                cin >> a[i][0] >> a[i][1];
                a[i][0]--, a[i][1]--;
        }
        for (int i = n - 1; i >= 0; i--) {
                mxR[i][0] = {a[i][1], i}, mnL[i][0] = {a[i][0], i};
                for (int j = 1; i + (1 << j) <= n; j++) {
                        mxR[i][j] = max(mxR[i][j - 1], mxR[i + (1 << j - 1)][j - 1]);
                        mnL[i][j] = min(mnL[i][j - 1], mnL[i + (1 << j - 1)][j - 1]);
                }
        }
        FOR(i, 0, n) {
                int x = minL(a[i][0], a[i][1]);
                assert(a[i][0] <= x && x <= a[i][1]);
                lft[i] = (!a[i][0] ? 0 : lft[x] + 1);
                isL[i] = isL[x] | !a[i][0];
                adj[x].push_back(i);
        }
        for (int i = n - 1; i >= 0; i--) {
                int x = maxR(a[i][0], a[i][1]);
                assert(a[i][0] <= x && x <= a[i][1]);
                rht[i] = (a[i][1] == n - 1 ? 0 : rht[x] + 1);
                isR[i] = isR[x] | (a[i][1] == n - 1);
                adj[x].push_back(i);
        }
        set<pair<int, int>> S;
        FOR(i, 0, n) {
                dist[i] = (isL[i] && isR[i] ? lft[i] + rht[i] + 1 : INF);
                S.insert({dist[i], i});
        }
        while (S.size()) {
                int v = S.begin()->second;
                S.erase(S.begin());
                for (auto u: adj[v]) if (dist[v] + 1 < dist[u]) {
                        S.erase({dist[u], u});
                        dist[u] = dist[v] + 1;
                        S.insert({dist[u], u});
                }
        }
        int q; cin >> q;
        while (q--) {
                int x; cin >> x; x--;
                cout << (dist[x] >= INF ? -1 : dist[x]) << '\n';
        }
        return 0;
}

Compilation message

passport.cpp: In function 'int main()':
passport.cpp:33:72: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   33 |                         mxR[i][j] = max(mxR[i][j - 1], mxR[i + (1 << j - 1)][j - 1]);
      |                                                                      ~~^~~
passport.cpp:34:72: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |                         mnL[i][j] = min(mnL[i][j - 1], mnL[i + (1 << j - 1)][j - 1]);
      |                                                                      ~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 182 ms 81076 KB Output is correct
5 Correct 145 ms 83512 KB Output is correct
6 Correct 114 ms 86620 KB Output is correct
7 Correct 105 ms 79296 KB Output is correct
8 Correct 81 ms 64912 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 8.0

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

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 182 ms 81076 KB Output is correct
5 Correct 145 ms 83512 KB Output is correct
6 Correct 114 ms 86620 KB Output is correct
7 Correct 105 ms 79296 KB Output is correct
8 Correct 81 ms 64912 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Incorrect 2 ms 4948 KB Output isn't correct
19 Halted 0 ms 0 KB -