oj.uz

Submission #1116746

# Submission time Handle Problem Language Result Execution time Memory
1116746 2024-11-22T10:22:35 Z hqminhuwu Passport (JOI23_passport) C++14
0 / 100
 686 ms 113948 KB 
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 5e5 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

int id[N], cnt;
vector <pii> a[N << 2];

void build (int i, int l, int r){
    cnt++;
    if (l == r){
        id[l] = i;
        return;
    }
    int mid = l + r >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    a[i << 1].pb({i, 0});
    a[i << 1 | 1].pb({i, 0});
}

void add (int i, int l, int r, int u, int v, int x){
    if (l > v || r < u) return;
    if (l >= u && r <= v){
        a[i].pb({x, 1});
        return;
    }
    int mid = l + r >> 1;
    add(i << 1, l, mid, u, v, x);
    add(i << 1 | 1, mid + 1, r, u, v, x);
}

int n, l[N], r[N], d[3][N];

void go (int z){
    priority_queue<pii, vector <pii>, greater<pii>> q;

    forr (i, 1, cnt){
        q.push({d[z][i], i});
    }

    while (!q.empty()) {
        pii t = q.top();
        q.pop();
        int u = t.nd;
        if (t.st != d[z][u] || t.st > n) continue;
        for (pii e : a[u]){
            int v = e.st, w = e.nd;
            if (minz(d[z][v], d[z][u] + w)){
                q.push({d[z][v], v});
            }
        }
    }
}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef kaguya
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n;

    build(1, 1, n);

    forr (i, 1, n){
        cin >> l[i] >> r[i];
        add(1, 1, n, l[i], r[i], id[i]);
    }

    memset (d, 63, sizeof d);
    d[0][id[1]] = 0;
    go(0);
    d[1][id[n]] = 0;
    go(1);
    
    forr (i, 1, n){
        int u = id[i];
        if (max(d[0][u], d[1][u]) > n){
            continue;
        }
        d[2][u] = d[1][u] + d[0][u] - (i != n && i != 1);
    }

    go(2);

    int qq, zz;
    cin >> qq;
    
    while (qq--){
        cin >> zz;
        zz = id[zz];
        cout << (d[2][zz] <= n ? d[2][zz] : -1) << "\n";
    }

    return 0;
}
/*



*/

Compilation message

passport.cpp: In function 'void build(int, int, int)':
passport.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: In function 'void add(int, int, int, int, int, int)':
passport.cpp:64:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 54608 KB Output is correct
2 Correct 17 ms 54608 KB Output is correct
3 Correct 21 ms 54488 KB Output is correct
4 Correct 686 ms 113948 KB Output is correct
5 Incorrect 439 ms 87284 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 54608 KB Output is correct
2 Correct 23 ms 54776 KB Output is correct
3 Correct 25 ms 54700 KB Output is correct
4 Correct 24 ms 54608 KB Output is correct
5 Correct 27 ms 54720 KB Output is correct
6 Correct 26 ms 54632 KB Output is correct
7 Correct 20 ms 54608 KB Output is correct
8 Correct 17 ms 54696 KB Output is correct
9 Correct 22 ms 54488 KB Output is correct
10 Correct 21 ms 54608 KB Output is correct
11 Correct 22 ms 54608 KB Output is correct
12 Correct 16 ms 54728 KB Output is correct
13 Correct 15 ms 54608 KB Output is correct
14 Incorrect 21 ms 54608 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 54608 KB Output is correct
2 Correct 23 ms 54776 KB Output is correct
3 Correct 25 ms 54700 KB Output is correct
4 Correct 24 ms 54608 KB Output is correct
5 Correct 27 ms 54720 KB Output is correct
6 Correct 26 ms 54632 KB Output is correct
7 Correct 20 ms 54608 KB Output is correct
8 Correct 17 ms 54696 KB Output is correct
9 Correct 22 ms 54488 KB Output is correct
10 Correct 21 ms 54608 KB Output is correct
11 Correct 22 ms 54608 KB Output is correct
12 Correct 16 ms 54728 KB Output is correct
13 Correct 15 ms 54608 KB Output is correct
14 Incorrect 21 ms 54608 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 54608 KB Output is correct
2 Correct 23 ms 54776 KB Output is correct
3 Correct 25 ms 54700 KB Output is correct
4 Correct 24 ms 54608 KB Output is correct
5 Correct 27 ms 54720 KB Output is correct
6 Correct 26 ms 54632 KB Output is correct
7 Correct 20 ms 54608 KB Output is correct
8 Correct 17 ms 54696 KB Output is correct
9 Correct 22 ms 54488 KB Output is correct
10 Correct 21 ms 54608 KB Output is correct
11 Correct 22 ms 54608 KB Output is correct
12 Correct 16 ms 54728 KB Output is correct
13 Correct 15 ms 54608 KB Output is correct
14 Incorrect 21 ms 54608 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 54608 KB Output is correct
2 Correct 17 ms 54608 KB Output is correct
3 Correct 21 ms 54488 KB Output is correct
4 Correct 686 ms 113948 KB Output is correct
5 Incorrect 439 ms 87284 KB Output isn't correct
6 Halted 0 ms 0 KB -