oj.uz

Submission #915297

# Submission time Handle Problem Language Result Execution time Memory
915297 2024-01-23T16:10:26 Z minhnhatnoe Passport (JOI23_passport) C++17
6 / 100
 144 ms 100692 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LG = 20;

vector<pair<int, int>> a[20], b[20];

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    a[0].resize(n), b[0].resize(n);
    for (int i=0; i<n; i++){
        cin >> a[0][i].first >> b[0][i].first;
        a[0][i].first--, b[0][i].first--;
        a[0][i].second = b[0][i].second = i;
    }

    for (int i=1; i<LG; i++){
        a[i].resize(n), b[i].resize(n);
        for (int j1=0, j2=1<<(i-1); j2<n; j1++, j2++){
            a[i][j1] = min(a[i-1][j1], a[i-1][j2]);
            b[i][j1] = max(b[i-1][j1], b[i-1][j2]);
        }
    }

    const int XX = 0;
    const int XY = XX + n;
    const int YX = XY + n;
    const int YY = YX + n;
    const int SIZE = YY + 1;

    vector<vector<pair<int, bool>>> g(SIZE);
    for (int i=0; i<n; i++){
        int l = a[0][i].first, r = b[0][i].first;
        int lg = 31 - __builtin_clz(r - l + 1);
        if (b[0][i].first == n-1){
            g[XY+i].emplace_back(XX+i, 0);
            g[YY].emplace_back(YX+i, 0);
        }
        else{
            int mxpos = max(b[lg][l], b[lg][r - (1 << lg) + 1]).second;
            g[XX+mxpos].emplace_back(XX+i, 1);
            g[XY+mxpos].emplace_back(XY+i, 1);
            g[YX+mxpos].emplace_back(YX+i, 1);
        }

        if (a[0][i].first == 0){
            g[YX+i].emplace_back(XX+i, 0);
            g[YY].emplace_back(XY+i, 0);
        }
        else{
            int mnpos = min(a[lg][l], a[lg][r - (1 << lg) + 1]).second;
            g[XX+mnpos].emplace_back(XX+i, 1);
            g[XY+mnpos].emplace_back(XY+i, 1);
            g[YX+mnpos].emplace_back(YX+i, 1);
        }
    }

    vector<int> dist(SIZE, INT_MAX);
    dist[YY] = 0;
    for (deque<int> q = {YY}; q.size();){
        int v = q.front(); q.pop_front();
        for (const pair<int, bool> &e: g[v]){
            if (dist[v] + e.second < dist[e.first]){
                dist[e.first] = dist[v] + e.second;
                if (e.second) q.push_back(e.first);
                else q.push_front(e.first);
            }
        }
    }

    int q; cin >> q;
    while (q--){
        int x; cin >> x; x--;
        if (dist[x] == INT_MAX) dist[x] = -2;
        cout << dist[x]+1 << "\n";
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 119 ms 93580 KB Output is correct
5 Correct 144 ms 98136 KB Output is correct
6 Correct 104 ms 100692 KB Output is correct
7 Correct 81 ms 95932 KB Output is correct
8 Correct 62 ms 75148 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 0 ms 456 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 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 1 ms 348 KB Output is correct
12 Incorrect 1 ms 604 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 0 ms 456 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 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 1 ms 348 KB Output is correct
12 Incorrect 1 ms 604 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 0 ms 456 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 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 1 ms 348 KB Output is correct
12 Incorrect 1 ms 604 KB Output isn't correct
13 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 119 ms 93580 KB Output is correct
5 Correct 144 ms 98136 KB Output is correct
6 Correct 104 ms 100692 KB Output is correct
7 Correct 81 ms 95932 KB Output is correct
8 Correct 62 ms 75148 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Incorrect 1 ms 604 KB Output isn't correct
21 Halted 0 ms 0 KB -