oj.uz

Submission #748228

# Submission time Handle Problem Language Result Execution time Memory
748228 2023-05-25T18:20:11 Z inventiontime Event Hopping (BOI22_events) C++17
20 / 100
 115 ms 24120 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][21];
    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

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 20416 KB Output is correct
2 Correct 112 ms 20408 KB Output is correct
3 Correct 88 ms 23548 KB Output is correct
4 Correct 85 ms 24120 KB Output is correct
5 Correct 115 ms 23864 KB Output is correct
6 Correct 108 ms 23708 KB Output is correct
7 Correct 111 ms 23616 KB Output is correct
8 Correct 111 ms 23904 KB Output is correct
9 Correct 54 ms 21796 KB Output is correct
10 Correct 82 ms 23320 KB Output is correct
11 Correct 83 ms 23208 KB Output is correct
12 Correct 82 ms 23328 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -