oj.uz

답안 #748224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
748224 2023-05-25T17:47:32 Z inventiontime Event Hopping (BOI22_events) C++17
0 / 100
 87 ms 19668 KB 
#include <bits/stdc++.h>
using namespace std;

#define int ll
#define endl '\n' //comment for interactive
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define pb push_back
#define re resize
#define ff first
#define ss second

#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)

#define print(x) cout << #x << ": " << x << endl << flush

typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef vector<vi> vvi;
typedef priority_queue<int> pq;

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }

const int inf = 1e17;

void solve() {

    int n, q;
    cin >> n >> q;
    vti event(n+1);
    loop1(i, n) {
        int s, e; cin >> s >> e;
        event[i] = {s, e, i};
    }
    sort(all1(event));
    event.pb({inf, inf});
    vi perm(n+1);
    loop1(i, n) {
        perm[event[i][2]] = i;
    }
    int rch[n+1][20];
    int idx = 1;
    loop1(i, n) {
        while(event[idx+1][0] <= event[i][1]
              and event[i][1] <= event[idx+1][1])
            idx++;
        rch[i][0] = idx;
    }

    loop1(j, 20) loop1(i, n) {
        rch[i][j] = rch[rch[i][j-1]][j-1];
    }

    while(q--) {
        int s, e;
        cin >> s >> e;
        s = perm[s];
        e = perm[e];
        if(s > e) {
            cout << "impossible" << endl;
        } else if(s == e) {
            cout << 0 << endl;
        } else {
            int x = s;
            int res = 0;
            for(int i = 20; i >= 0; i--) if(rch[x][i] < e) {
                res += 1 << i;
                x = rch[x][i];
            }

            if(e <= rch[x][0]) res++;
            else res = -1;
            
            if(res != -1) cout << res << endl;
            else cout << "impossible" << endl;
        }
    }

}

signed main() {

    fast_io;

    int t = 1; //cin >> t;
    while(t--)
        solve();

    return 0;

}

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 0 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 0 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 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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