oj.uz

답안 #696597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
696597 2023-02-07T00:55:21 Z jhwest2 Event Hopping (BOI22_events) C++17
20 / 100
 130 ms 18056 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 101010;

int n, q, l[N], r[N], w[N], go[20][N], ans[N];
vector<array<int, 2>> query[N];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) 
        cin >> l[i] >> r[i];
    
    iota(w + 1, w + 1 + n, 1);
    sort(w + 1, w + 1 + n, [&](auto i, auto j) {
        return r[i] < r[j];
    });

    for (int i = 0; i < q; i++) {
        int s, e; cin >> s >> e;
        if (s != e) {
            if (r[s] <= r[e])
                query[e].push_back({s, i});
            else
                ans[i] = 1e9;
        }
    }
    vector<int> v;
    for (int i = 1; i <= n; i++) {
        while (!v.empty() && l[v.back()] >= l[w[i]])
            v.pop_back();
        v.push_back(w[i]);

        int L = 0, R = (int)v.size() - 1;
        while (L < R) {
            int M = (L + R) / 2;
            if (r[v[M]] < l[w[i]])
                L = M + 1;
            else
                R = M;
        }
        go[0][w[i]] = v[L];
        for (int j = 1; j < 20; j++)
            go[j][w[i]] = go[j - 1][go[j - 1][w[i]]];

        for (auto [s, t] : query[w[i]]) {
            int x = w[i];
            for (int j = 19; j >= 0; j--) {
                if (r[s] < l[go[j][x]]) {
                    x = go[j][x];
                    ans[t] += (1 << j);
                }
            }
            ans[t] += (r[s] < l[x]) ? 2 : 1;
        }
    }
    for (int i = 0; i < q; i++) {
        if (ans[i] > n)
            cout << "impossible\n";
        else
            cout << ans[i] << '\n';
    }
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 109 ms 17564 KB Output is correct
3 Correct 108 ms 17472 KB Output is correct
4 Correct 114 ms 17864 KB Output is correct
5 Correct 91 ms 17508 KB Output is correct
6 Correct 96 ms 17472 KB Output is correct
7 Correct 93 ms 17536 KB Output is correct
8 Incorrect 77 ms 17900 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2700 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2840 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Incorrect 3 ms 2900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2700 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2840 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Incorrect 3 ms 2900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2700 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2840 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Incorrect 3 ms 2900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 17576 KB Output is correct
2 Correct 105 ms 17420 KB Output is correct
3 Correct 130 ms 18056 KB Output is correct
4 Correct 84 ms 17988 KB Output is correct
5 Correct 111 ms 17840 KB Output is correct
6 Correct 129 ms 17644 KB Output is correct
7 Correct 110 ms 17880 KB Output is correct
8 Correct 91 ms 17680 KB Output is correct
9 Correct 49 ms 14284 KB Output is correct
10 Correct 83 ms 17184 KB Output is correct
11 Correct 79 ms 17124 KB Output is correct
12 Correct 84 ms 17176 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 109 ms 17564 KB Output is correct
3 Correct 108 ms 17472 KB Output is correct
4 Correct 114 ms 17864 KB Output is correct
5 Correct 91 ms 17508 KB Output is correct
6 Correct 96 ms 17472 KB Output is correct
7 Correct 93 ms 17536 KB Output is correct
8 Incorrect 77 ms 17900 KB Output isn't correct
9 Halted 0 ms 0 KB -