oj.uz

Submission #602670

# Submission time Handle Problem Language Result Execution time Memory
602670 2022-07-23T10:00:09 Z shrimb Event Hopping (BOI22_events) C++17
20 / 100
 143 ms 28336 KB 
#include"bits/stdc++.h"
using namespace std;
const int maxn = 200001;
const int N = exp2(ceil(log2(maxn)));
pair<int,int> seg[2 * N], Val;
int Left, Right, Pos;
pair<int,int> Query (int l = 1, int r = N, int ind = 1) {
    if (l > Right || r < Left) return pair<int,int>{-1, -1};
    if (l >= Left and r <= Right) return seg[ind];
    int m = (l + r) / 2;
    return max(Query(l, m, ind * 2), Query(m + 1, r, ind * 2 + 1));
}
void Update () {
    int ind = N + Pos - 1;
    seg[ind] = Val;
    while (ind /= 2) seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
}
int Sparse[maxn][22];
signed main () {
    cin.tie(0) -> sync_with_stdio(0);
    for (auto& [i, j] : seg) i = j = -1;
    memset(Sparse, -1, sizeof Sparse);
    int n, q;
    cin >> n >> q;
    pair<int,int> a[n];

    vector<int*> v;
    for (auto& [i, j] : a) {
        cin >> i >> j;
        v.push_back(&i);
        v.push_back(&j);
    }
    sort(v.begin(), v.end(), [](int*i,int*j){return *i<*j;});
    int prev = -1;
    int id = 0;
    for (auto & i : v) {
        if (*i != prev) id++;
        prev=*i;
        *i = id;
    }
    int P[n + 1];
    for (int i = 1 ; i <= n ; i++) P[i] = i - 1;
    sort(P + 1, P + 1 + n, [&](int i, int j){return a[i] < a[j];});
    int conv[n + 1];
    for (int i = 1 ; i <= n ; i++) conv[P[i] + 1] = i - 1;
    sort(a, a + n);
    // cerr << "conv: ";
    // for (int i = 1 ; i <= n ; i++) cerr << conv[i] << " ";
    // cerr << "\n";
    Left = 1;
    for (int i = n - 1 ; i >= 0 ; i--) {
        if (i < n - 1) {
            Right = a[i].second;
            Sparse[i][0] = Query().second;
        }
        Pos = a[i].first;
        Val = {a[i].second, i};
        Update();
    }
    for (int j = 1 ; j < 20 ; j++) {
        for (int i = 0 ; i < n ; i++) {
            if (Sparse[i][j-1] != -1) Sparse[i][j] = Sparse[Sparse[i][j-1]][j-1];
            // cerr << i << " " << j << ": " << Sparse[i][j] << endl;
        }
    }
    // cout << "~~~~~~~~~~~\n";
    // for (int i = 0 ; i < n ; i++) {
    //     cout << a[i].first << " " << a[i].second << endl;
    // }
    // // cout << "~~~~~~~~~~~~\n";
    // for (int i = 0 ; i < n ; i++) {
    //     cout << Sparse[i][0] << " ";
    // }
    // cout << '\n';
    while (q--) {
        int i, j;
        cin >> i >> j;
        // cerr << "conv: " << i << " " << j << '\n';
        i = conv[i], j = conv[j];
        // cerr << "conv: " << i << " " << j << '\n';
        if (i == j) {
            cout << 0 << endl;
            continue;
        }
        if (a[j].second < a[i].second) {
            cout << "impossible\n";
            continue;
        }
        if (a[j].first <= a[i].second and a[j].second >= a[i].second) {
            cout << 1 << '\n';
            continue;
        }
        int cnt = 0;
        for (int k = 19 ; k >= 0 ; k--) {
            if (Sparse[i][k] != -1) {
                if (a[Sparse[i][k]].second < a[j].first) {
                    // cerr << Sparse[i][k] << endl;
                    // cerr << i << " " << k << endl;
                    cnt += (1 << k);
                    i = Sparse[i][k];
                }
            }
        }
        // cerr << "debug: " << i << " " << cnt << endl;
        if (Sparse[i][0] != -1 and a[Sparse[i][0]].second >= a[j].first and a[Sparse[i][0]].second <= a[j].second) {
            cout << cnt + 2 - (Sparse[i][0] == j) << '\n';

        } else {
            cout << "impossible\n";
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21588 KB Output is correct
2 Correct 114 ms 25388 KB Output is correct
3 Correct 113 ms 25524 KB Output is correct
4 Correct 118 ms 25396 KB Output is correct
5 Incorrect 115 ms 25536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21568 KB Output is correct
2 Correct 9 ms 21588 KB Output is correct
3 Correct 9 ms 21664 KB Output is correct
4 Correct 9 ms 21588 KB Output is correct
5 Incorrect 10 ms 21572 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21568 KB Output is correct
2 Correct 9 ms 21588 KB Output is correct
3 Correct 9 ms 21664 KB Output is correct
4 Correct 9 ms 21588 KB Output is correct
5 Incorrect 10 ms 21572 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21568 KB Output is correct
2 Correct 9 ms 21588 KB Output is correct
3 Correct 9 ms 21664 KB Output is correct
4 Correct 9 ms 21588 KB Output is correct
5 Incorrect 10 ms 21572 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 25500 KB Output is correct
2 Correct 117 ms 25416 KB Output is correct
3 Correct 122 ms 25412 KB Output is correct
4 Correct 106 ms 25920 KB Output is correct
5 Correct 143 ms 25792 KB Output is correct
6 Correct 132 ms 25664 KB Output is correct
7 Correct 134 ms 25592 KB Output is correct
8 Correct 132 ms 25672 KB Output is correct
9 Correct 88 ms 26680 KB Output is correct
10 Correct 112 ms 28320 KB Output is correct
11 Correct 117 ms 28116 KB Output is correct
12 Correct 126 ms 28336 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21588 KB Output is correct
2 Correct 114 ms 25388 KB Output is correct
3 Correct 113 ms 25524 KB Output is correct
4 Correct 118 ms 25396 KB Output is correct
5 Incorrect 115 ms 25536 KB Output isn't correct
6 Halted 0 ms 0 KB -