oj.uz

Submission #1109445

# Submission time Handle Problem Language Result Execution time Memory
1109445 2024-11-06T17:53:33 Z Pekiban Passport (JOI23_passport) C++17
46 / 100
 530 ms 102328 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 8e5+5;
vector<array<int, 3>> g[N];
bool vis[N];
int di[N], ri[N], f[N], lc[N], rc[N], n, C;
void add(int u, int v, int x, int R = -1) {
    g[u].push_back({v, x, R});
}
int build(int l = 1, int r = n) {
    if (l == r) return l;
    int m = (l+r)/2, nd = ++C;
    lc[nd] = build(l, m);
    rc[nd] = build(m+1, r);
    add(lc[nd], nd, 0);
    add(rc[nd], nd, 0);
    return nd;
}
void Add(int l, int r, int u, int i = n+1, int l2 = 1, int r2 = n) {
    if (l <= l2 && r2 <= r) {
        add(i, u, 1, r);
        return;
    } 
    int m2 = (l2 + r2)/2;
    if (l <= m2)    Add(l, r, u, lc[i], l2, m2);
    if (m2+1 <= r)  Add(l, r, u, rc[i], m2+1, r2);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n; C = n;
    int L[n+1], R[n+1];
    build();
    for (int i = 1; i <= n; ++i) {
        cin >> L[i] >> R[i];
        Add(L[i], R[i], i);
    }
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> pq;
    fill(di, di+C+1, 1e9);
    for (int i = 1; i <= n; ++i) {
        if (L[i] == 1) {
            ri[i] = R[i], di[i] = 1;
            pq.push({1, i});
        }
    }
    while (!pq.empty()) {
        auto [D, s] = pq.top(); pq.pop();
        if (vis[s]) continue;
        vis[s] = 1;
        for (auto [u, w, Ri] : g[s]) {
            if (di[u] > di[s] + w) {
                di[u] = di[s] + w;
                pq.push({di[u], u});
            }
            if (di[u] == di[s] + w) ri[u] = max({ri[u], ri[s], Ri});
        }
    }
    multiset<int> ms, vs;
    for (int i = 1; i <= n; ++i)    ms.insert(R[i]);
    fill(f, f+n+1, 1e9);
    f[n] = 0;
    vs.insert(0);
    for (int i = n; i >= 1; --i) {
        if (i != n) {
            f[i] = (vs.empty() ? 1e9 : *vs.begin()) +1;
            vs.insert(f[i]);
        }
        if (i == 1) continue;
        int RRR = *ms.rbegin();
        ms.erase(ms.find(R[i]));
        while (RRR != *ms.rbegin()) {
            vs.erase(vs.find(f[RRR]));
            RRR--;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << (di[x] + f[ri[x]] > 5e5 ? -1 : di[x] + f[ri[x]]) << '\n';
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 7 ms 29264 KB Output is correct
3 Correct 5 ms 29264 KB Output is correct
4 Correct 530 ms 102328 KB Output is correct
5 Correct 214 ms 72576 KB Output is correct
6 Correct 144 ms 64080 KB Output is correct
7 Correct 172 ms 62648 KB Output is correct
8 Correct 162 ms 71080 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 5 ms 29264 KB Output is correct
3 Correct 5 ms 29124 KB Output is correct
4 Correct 5 ms 29264 KB Output is correct
5 Correct 5 ms 29340 KB Output is correct
6 Correct 5 ms 29264 KB Output is correct
7 Correct 4 ms 29264 KB Output is correct
8 Correct 5 ms 29264 KB Output is correct
9 Correct 5 ms 29264 KB Output is correct
10 Correct 4 ms 29264 KB Output is correct
11 Correct 5 ms 29264 KB Output is correct
12 Correct 5 ms 29436 KB Output is correct
13 Correct 5 ms 29408 KB Output is correct
14 Correct 5 ms 29440 KB Output is correct
15 Correct 5 ms 29264 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 5 ms 29264 KB Output is correct
3 Correct 5 ms 29124 KB Output is correct
4 Correct 5 ms 29264 KB Output is correct
5 Correct 5 ms 29340 KB Output is correct
6 Correct 5 ms 29264 KB Output is correct
7 Correct 4 ms 29264 KB Output is correct
8 Correct 5 ms 29264 KB Output is correct
9 Correct 5 ms 29264 KB Output is correct
10 Correct 4 ms 29264 KB Output is correct
11 Correct 5 ms 29264 KB Output is correct
12 Correct 5 ms 29436 KB Output is correct
13 Correct 5 ms 29408 KB Output is correct
14 Correct 5 ms 29440 KB Output is correct
15 Correct 5 ms 29264 KB Output is correct
16 Correct 7 ms 30032 KB Output is correct
17 Correct 7 ms 29776 KB Output is correct
18 Correct 8 ms 30032 KB Output is correct
19 Correct 7 ms 30032 KB Output is correct
20 Correct 6 ms 29624 KB Output is correct
21 Correct 7 ms 29788 KB Output is correct
22 Correct 6 ms 29520 KB Output is correct
23 Correct 7 ms 29776 KB Output is correct
24 Correct 6 ms 29896 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 5 ms 29264 KB Output is correct
3 Correct 5 ms 29124 KB Output is correct
4 Correct 5 ms 29264 KB Output is correct
5 Correct 5 ms 29340 KB Output is correct
6 Correct 5 ms 29264 KB Output is correct
7 Correct 4 ms 29264 KB Output is correct
8 Correct 5 ms 29264 KB Output is correct
9 Correct 5 ms 29264 KB Output is correct
10 Correct 4 ms 29264 KB Output is correct
11 Correct 5 ms 29264 KB Output is correct
12 Correct 5 ms 29436 KB Output is correct
13 Correct 5 ms 29408 KB Output is correct
14 Correct 5 ms 29440 KB Output is correct
15 Correct 5 ms 29264 KB Output is correct
16 Correct 7 ms 30032 KB Output is correct
17 Correct 7 ms 29776 KB Output is correct
18 Correct 8 ms 30032 KB Output is correct
19 Correct 7 ms 30032 KB Output is correct
20 Correct 6 ms 29624 KB Output is correct
21 Correct 7 ms 29788 KB Output is correct
22 Correct 6 ms 29520 KB Output is correct
23 Correct 7 ms 29776 KB Output is correct
24 Correct 6 ms 29896 KB Output is correct
25 Correct 4 ms 29264 KB Output is correct
26 Correct 5 ms 29264 KB Output is correct
27 Incorrect 8 ms 29864 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 7 ms 29264 KB Output is correct
3 Correct 5 ms 29264 KB Output is correct
4 Correct 530 ms 102328 KB Output is correct
5 Correct 214 ms 72576 KB Output is correct
6 Correct 144 ms 64080 KB Output is correct
7 Correct 172 ms 62648 KB Output is correct
8 Correct 162 ms 71080 KB Output is correct
9 Correct 5 ms 29264 KB Output is correct
10 Correct 5 ms 29264 KB Output is correct
11 Correct 5 ms 29124 KB Output is correct
12 Correct 5 ms 29264 KB Output is correct
13 Correct 5 ms 29340 KB Output is correct
14 Correct 5 ms 29264 KB Output is correct
15 Correct 4 ms 29264 KB Output is correct
16 Correct 5 ms 29264 KB Output is correct
17 Correct 5 ms 29264 KB Output is correct
18 Correct 4 ms 29264 KB Output is correct
19 Correct 5 ms 29264 KB Output is correct
20 Correct 5 ms 29436 KB Output is correct
21 Correct 5 ms 29408 KB Output is correct
22 Correct 5 ms 29440 KB Output is correct
23 Correct 5 ms 29264 KB Output is correct
24 Correct 7 ms 30032 KB Output is correct
25 Correct 7 ms 29776 KB Output is correct
26 Correct 8 ms 30032 KB Output is correct
27 Correct 7 ms 30032 KB Output is correct
28 Correct 6 ms 29624 KB Output is correct
29 Correct 7 ms 29788 KB Output is correct
30 Correct 6 ms 29520 KB Output is correct
31 Correct 7 ms 29776 KB Output is correct
32 Correct 6 ms 29896 KB Output is correct
33 Correct 4 ms 29264 KB Output is correct
34 Correct 5 ms 29264 KB Output is correct
35 Incorrect 8 ms 29864 KB Output isn't correct
36 Halted 0 ms 0 KB -