oj.uz

Submission #803089

# Submission time Handle Problem Language Result Execution time Memory
803089 2023-08-02T21:33:51 Z lukameladze Passport (JOI23_passport) C++17
48 / 100
 335 ms 63236 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int,int>
#define pb push_back
const int N = 1e5 + 5;
int n, l[N], r[N];
pii tree[4 * N];
multiset <pii> ms[4 * N];
void update(int node, int le, int ri, int idx, int val, int id) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        // cout<<"upd "<<le<<" "<<ri<<" "<<node<<"\n";
        if (val == 0) {
            if (!ms[node].size()) {
                // cout<<node<<" "<<idx<<" "<<val<<" "<<id<<"\n";
                // exit(0);
                assert(false);
            }
            assert(ms[node].size());
            ms[node].erase(--ms[node].end());
            if (!ms[node].size()) {
                tree[node] = {0, 0}; return ;
            }
        } 
        if (val != 0) ms[node].insert({val, id});
        auto it = --ms[node].end();
        tree[node] = {(*it).f, (*it).s};
        return ;
    }
    int mid = (le + ri) / 2;
    update(2 * node, le, mid, idx, val, id);
    update(2 * node + 1, mid + 1, ri, idx, val, id);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
pii getans(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return {0, 0};
    if (le >= start && ri <= end) return tree[node];
    int mid = (le + ri) / 2;
    return max(getans(2 * node, le, mid, start, end), getans(2 * node + 1, mid + 1, ri ,start, end));
}
int dp[2][N];
void bfs(int a, int ty) {
    for (int i = 0; i < 4 * N; i++) {
        tree[i] = {0, 0}; 
        ms[i].clear();
    }
    for (int i = 1; i <= n; i++) {
        if (i == a) continue;
        dp[ty][i] = 1e9;
        update(1, 1, n, l[i], r[i], i);
    }
    
    queue <int> q;
    q.push(a);
    dp[ty][a] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        while (getans(1, 1, n, 1, x).f >= x) {
            pii sth = getans(1, 1, n, 1, x);
            q.push(sth.s);
            dp[ty][sth.s] = dp[ty][x] + 1;
            update(1, 1, n, l[sth.s], 0, sth.s);
        }
    }
}

int tree_mn[4 * N];
void upd_mn(int node, int le, int ri, int idx, int val) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        tree_mn[node] = val; return ;
    }
    int mid = (le + ri) / 2;
    upd_mn(2 * node, le, mid, idx,val);
    upd_mn(2 * node + 1, mid + 1, ri, idx,val);
    tree_mn[node] = min(tree_mn[2 * node], tree_mn[2 * node + 1]);
}
int get_mn(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return 1e9;
    if (le >= start && ri <= end) return tree_mn[node];
    int mid = (le + ri) / 2;
    return min(get_mn(2 * node, le ,mid, start, end), get_mn(2 * node + 1, mid + 1, ri, start, end));
}
signed main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>l[i]>>r[i];
    }
    bfs(1, 0);
    bfs(n, 1);
    vector <pii> vec;
    for (int i = 1; i <= n; i++) {
        vec.pb({dp[0][i] + dp[1][i] - (i != 1 && i != n), i});
    }
    sort(vec.begin(), vec.end());
    for (pii sth : vec) {
        upd_mn(1, 1, n, sth.s, sth.f);
    }
    vector <int> res(n + 5, 0);
    for (int i = 0; i < (int)vec.size(); i++) {
        int id = vec[i].s;
        res[id] = min(vec[i].f, get_mn(1, 1, n, l[id], r[id]) + 1);
        upd_mn(1, 1, n, id, res[id]);
    }
    int q;
    cin>>q;
    while(q--) {
        int idx; cin>>idx;
        cout<<(res[idx] >= 1e9 ? -1 : res[idx])<<"\n";
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22228 KB Output is correct
2 Correct 14 ms 22228 KB Output is correct
3 Correct 14 ms 22192 KB Output is correct
4 Runtime error 335 ms 63236 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 22252 KB Output is correct
2 Correct 14 ms 22228 KB Output is correct
3 Correct 14 ms 22244 KB Output is correct
4 Correct 14 ms 22160 KB Output is correct
5 Correct 14 ms 22156 KB Output is correct
6 Correct 14 ms 22196 KB Output is correct
7 Correct 13 ms 22204 KB Output is correct
8 Correct 17 ms 22200 KB Output is correct
9 Correct 14 ms 22188 KB Output is correct
10 Correct 16 ms 22220 KB Output is correct
11 Correct 15 ms 22196 KB Output is correct
12 Correct 14 ms 22196 KB Output is correct
13 Correct 14 ms 22264 KB Output is correct
14 Correct 15 ms 22208 KB Output is correct
15 Correct 14 ms 22228 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 22252 KB Output is correct
2 Correct 14 ms 22228 KB Output is correct
3 Correct 14 ms 22244 KB Output is correct
4 Correct 14 ms 22160 KB Output is correct
5 Correct 14 ms 22156 KB Output is correct
6 Correct 14 ms 22196 KB Output is correct
7 Correct 13 ms 22204 KB Output is correct
8 Correct 17 ms 22200 KB Output is correct
9 Correct 14 ms 22188 KB Output is correct
10 Correct 16 ms 22220 KB Output is correct
11 Correct 15 ms 22196 KB Output is correct
12 Correct 14 ms 22196 KB Output is correct
13 Correct 14 ms 22264 KB Output is correct
14 Correct 15 ms 22208 KB Output is correct
15 Correct 14 ms 22228 KB Output is correct
16 Correct 18 ms 22460 KB Output is correct
17 Correct 18 ms 22468 KB Output is correct
18 Correct 18 ms 22404 KB Output is correct
19 Correct 18 ms 22428 KB Output is correct
20 Correct 21 ms 22368 KB Output is correct
21 Correct 17 ms 22432 KB Output is correct
22 Correct 16 ms 22484 KB Output is correct
23 Correct 17 ms 22440 KB Output is correct
24 Correct 17 ms 22480 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 22252 KB Output is correct
2 Correct 14 ms 22228 KB Output is correct
3 Correct 14 ms 22244 KB Output is correct
4 Correct 14 ms 22160 KB Output is correct
5 Correct 14 ms 22156 KB Output is correct
6 Correct 14 ms 22196 KB Output is correct
7 Correct 13 ms 22204 KB Output is correct
8 Correct 17 ms 22200 KB Output is correct
9 Correct 14 ms 22188 KB Output is correct
10 Correct 16 ms 22220 KB Output is correct
11 Correct 15 ms 22196 KB Output is correct
12 Correct 14 ms 22196 KB Output is correct
13 Correct 14 ms 22264 KB Output is correct
14 Correct 15 ms 22208 KB Output is correct
15 Correct 14 ms 22228 KB Output is correct
16 Correct 18 ms 22460 KB Output is correct
17 Correct 18 ms 22468 KB Output is correct
18 Correct 18 ms 22404 KB Output is correct
19 Correct 18 ms 22428 KB Output is correct
20 Correct 21 ms 22368 KB Output is correct
21 Correct 17 ms 22432 KB Output is correct
22 Correct 16 ms 22484 KB Output is correct
23 Correct 17 ms 22440 KB Output is correct
24 Correct 17 ms 22480 KB Output is correct
25 Correct 14 ms 22264 KB Output is correct
26 Correct 13 ms 22200 KB Output is correct
27 Correct 18 ms 22484 KB Output is correct
28 Correct 18 ms 22460 KB Output is correct
29 Correct 20 ms 22444 KB Output is correct
30 Correct 21 ms 22440 KB Output is correct
31 Correct 18 ms 22476 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22228 KB Output is correct
2 Correct 14 ms 22228 KB Output is correct
3 Correct 14 ms 22192 KB Output is correct
4 Runtime error 335 ms 63236 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -