oj.uz

답안 #721878

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721878 2023-04-11T08:11:20 Z MDSPro Event Hopping (BOI22_events) C++17
20 / 100
 95 ms 12256 KB 
#include "bits/stdc++.h"
 
using namespace std;
 
int main(){
    cin.tie(0)->sync_with_stdio(0);
 
    int n,q; cin >> n >> q;
    vector<tuple<int,int,int>> ev;
    for(int i = 0; i < n; ++i){
        int x,y; cin >> x >> y;
        ev.emplace_back(x,y,i+1);
    }
 
    sort(ev.begin(),ev.end());  
 
    vector<int> nw_order(n+1);
    vector<int> left(n),right(n);
    for(int i = 0; i < n; ++i) {
        left[i] = get<0>(ev[i]);
        right[i] = get<1>(ev[i]);
        nw_order[get<2>(ev[i])] = i;
    }
 
    vector<vector<int>> nxt(20,vector<int>(n+1));
    nxt[0][n] = n;
 
    int r = 0;
    for(int i = 0; i < n; ++i){
        while(r+1 < n && left[r+1] <= right[i]) r++;

        if(i != r) nxt[0][i] = r;
        else nxt[0][i] = n;
    }
    for(int i = 1; i < 20; ++i) {
        for(int j = 0; j <= n; ++j){
            nxt[i][j] = nxt[i-1][nxt[i-1][j]];
        }
    }
 
    auto get = [&](int x, int y){
        if(x == y) return 0;
        if(x > y) return -1;
        if(nxt[0][x] == n) return -1;
        if(nxt[0][x] > y) return 1;

        int cur = 0;
        for(int i = 19; i >= 0; --i){
            if(x == y) return cur;
            if(nxt[i][x] <= y) {
                cur |= (1<<i);
                x = nxt[i][x];
            }
        }
 

        if(x == y) return cur;
        if(nxt[0][x] == n) return -1;
        return cur+1;
    };
 
    while(q--){
        int a,b; cin >> a >> b;
        a = nw_order[a];
        b = nw_order[b];
 
        int ans = get(a,b);
        if(ans == -1) cout << "impossible\n";
        else cout << ans << '\n';
    }
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 11940 KB Output is correct
2 Correct 81 ms 11604 KB Output is correct
3 Correct 69 ms 11604 KB Output is correct
4 Correct 57 ms 12236 KB Output is correct
5 Correct 95 ms 11948 KB Output is correct
6 Correct 88 ms 12136 KB Output is correct
7 Correct 81 ms 12044 KB Output is correct
8 Correct 71 ms 12256 KB Output is correct
9 Correct 34 ms 11324 KB Output is correct
10 Correct 67 ms 11732 KB Output is correct
11 Correct 59 ms 11492 KB Output is correct
12 Correct 60 ms 11704 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -