oj.uz

답안 #602679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
602679 2022-07-23T10:05:45 Z shrimb Event Hopping (BOI22_events) C++17
20 / 100
 180 ms 26052 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 (i == j) {
            cout << cnt << endl;
        }
        else 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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 21588 KB Output is correct
2 Correct 118 ms 25484 KB Output is correct
3 Correct 112 ms 25396 KB Output is correct
4 Correct 122 ms 25416 KB Output is correct
5 Incorrect 124 ms 25588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21632 KB Output is correct
2 Correct 9 ms 21536 KB Output is correct
3 Correct 12 ms 21588 KB Output is correct
4 Correct 10 ms 21592 KB Output is correct
5 Incorrect 10 ms 21588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21632 KB Output is correct
2 Correct 9 ms 21536 KB Output is correct
3 Correct 12 ms 21588 KB Output is correct
4 Correct 10 ms 21592 KB Output is correct
5 Incorrect 10 ms 21588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21632 KB Output is correct
2 Correct 9 ms 21536 KB Output is correct
3 Correct 12 ms 21588 KB Output is correct
4 Correct 10 ms 21592 KB Output is correct
5 Incorrect 10 ms 21588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 25480 KB Output is correct
2 Correct 130 ms 25416 KB Output is correct
3 Correct 124 ms 25488 KB Output is correct
4 Correct 111 ms 26052 KB Output is correct
5 Correct 180 ms 25836 KB Output is correct
6 Correct 134 ms 25572 KB Output is correct
7 Correct 135 ms 25580 KB Output is correct
8 Correct 128 ms 25676 KB Output is correct
9 Correct 92 ms 24884 KB Output is correct
10 Correct 130 ms 25268 KB Output is correct
11 Correct 113 ms 25072 KB Output is correct
12 Correct 141 ms 25284 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 21588 KB Output is correct
2 Correct 118 ms 25484 KB Output is correct
3 Correct 112 ms 25396 KB Output is correct
4 Correct 122 ms 25416 KB Output is correct
5 Incorrect 124 ms 25588 KB Output isn't correct
6 Halted 0 ms 0 KB -