oj.uz

Submission #857648

# Submission time Handle Problem Language Result Execution time Memory
857648 2023-10-06T15:08:46 Z vgtcross Event Hopping (BOI22_events) C++17
20 / 100
 206 ms 27664 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 100100;
const int K = 18;

int jmp[K][N];

struct segtree {
    pii v;
    int l, r, m;
    segtree *lc = nullptr, *rc = nullptr;
    
    segtree(int L, int R, vector<int> &u){
        l = L;
        r = R;
        m = (l + r) / 2;
        if (l == r) {
            v = {u[m], m};
            return;
        }
        
        lc = new segtree(l, m, u);
        rc = new segtree(m+1, r, u);
        v = min(lc->v, rc->v);
    }
    
    pii range_min(int L, int R) {
        if (L > R) return {2e9, 2e9};
        if (l == L && r == R) return v;
        return min(lc->range_min(L, min(R, m)), rc->range_min(max(m+1, L), R));
    }
    
    void del() {
        if (lc != nullptr) lc->del();
        if (rc != nullptr) rc->del();
        delete lc;
        delete rc;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    
    vector<array<int, 3>> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i][1] >> v[i][0];
        v[i][2] = i+1;
    }
    sort(v.begin(), v.end());
    
    vector<int> pos(n+1);
    vector<int> d(n);
    set<pii> st;
    for (int i = 0; i < n; ++i) {
        st.insert({v[i][0], i});
        pii b = *st.lower_bound({v[i][1], -1});
        d[i] = b.second;
        pos[v[i][2]] = i;
    }
    
    segtree seg(0, n-1, d);
    for (int i = 0; i < n; ++i) {
        jmp[0][i] = seg.range_min(d[i], i).second;
    }
    
    for (int i = 1; i < K; ++i) {
        for (int j = 0; j < n; ++j) jmp[i][j] = jmp[i-1][jmp[i-1][j]];
    }
    
    while (q--) {
        int a, b;
        cin >> a >> b;
        a = pos[a];
        b = pos[b];
        
        if (a > b) {
            cout << "impossible\n";
            continue;
        } else if (a == b) {
            cout << "0\n";
            continue;
        } else if (d[b] <= a) {
            cout << "1\n";
            continue;
        }
        
        int ans = 0;
        for (int i = K-1; i >= 0; --i) {
            if (a < d[jmp[i][b]]) {
                b = jmp[i][b];
                ans += 1 << i;
            }
        }
        
        b = jmp[0][b];
        
        if (a < d[b]) cout << "impossible\n";
        else cout << ans+2 << '\n';
        cout << flush;
    }
    
    seg.del();
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 193 ms 27104 KB Output is correct
3 Correct 189 ms 27168 KB Output is correct
4 Correct 206 ms 27312 KB Output is correct
5 Correct 201 ms 27324 KB Output is correct
6 Correct 198 ms 27328 KB Output is correct
7 Correct 199 ms 27440 KB Output is correct
8 Correct 187 ms 27544 KB Output is correct
9 Correct 192 ms 27536 KB Output is correct
10 Correct 155 ms 27540 KB Output is correct
11 Incorrect 144 ms 27476 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 27220 KB Output is correct
2 Correct 191 ms 27016 KB Output is correct
3 Correct 206 ms 27364 KB Output is correct
4 Correct 194 ms 27664 KB Output is correct
5 Correct 144 ms 27592 KB Output is correct
6 Correct 160 ms 27380 KB Output is correct
7 Correct 160 ms 27320 KB Output is correct
8 Correct 148 ms 27476 KB Output is correct
9 Correct 66 ms 25384 KB Output is correct
10 Correct 198 ms 26864 KB Output is correct
11 Correct 197 ms 26712 KB Output is correct
12 Correct 206 ms 27268 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 193 ms 27104 KB Output is correct
3 Correct 189 ms 27168 KB Output is correct
4 Correct 206 ms 27312 KB Output is correct
5 Correct 201 ms 27324 KB Output is correct
6 Correct 198 ms 27328 KB Output is correct
7 Correct 199 ms 27440 KB Output is correct
8 Correct 187 ms 27544 KB Output is correct
9 Correct 192 ms 27536 KB Output is correct
10 Correct 155 ms 27540 KB Output is correct
11 Incorrect 144 ms 27476 KB Output isn't correct
12 Halted 0 ms 0 KB -