oj.uz

Submission #656537

# Submission time Handle Problem Language Result Execution time Memory
656537 2022-11-07T22:48:16 Z Lobo Event Hopping (BOI22_events) C++17
20 / 100
 129 ms 28808 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 1e5+10;

int n, q, idord[maxn], lf[maxn], rg[maxn], nx[maxn][25];

void solve() {
    cin >> n >> q;
    vector<pair<pair<int,int>,int>> ord;
    for(int i = 1; i <= n; i++) {
        int l, r; cin >> l >> r;
        ord.pb(mp(mp(r,l),i));
    }
    sort(all(ord));
    for(int i = 1; i <= n; i++) {
        idord[ord[i-1].sc] = i;
        lf[i] = ord[i-1].fr.sc;
        rg[i] = ord[i-1].fr.fr;
    }

    for(int i = 1; i <= n; i++) {
        nx[i][0] = 0;
        int l = i+1;
        int r = n;
        while(l <= r) {
            int mid = (l+r)/2;
            if(lf[mid] <= rg[i]) {
                nx[i][0] = mid;
                l = mid+1;
            }
            else {
                r = mid-1;
            }
        }
    }

    for(int j = 1; j <= 20; j++) {
        for(int i = 1; i <= n; i++) {
            nx[i][j] = nx[nx[i][j-1]][j-1];
        }
    }

    while(q--) {
        int s,e; cin >> s >> e;
        s = idord[s];
        e = idord[e];

        int ans = 0;
        for(int j = 20; j >= 0; j--) {
            if(nx[s][j] != 0 && rg[nx[s][j]] <= rg[e]) {
                ans+= (1<<j);
                s = nx[s][j];
            }
        }

        if(s == e) {
            cout << ans << endl;
        }
        else if(lf[e] <= rg[s] && rg[s] <= rg[e]) {
            cout << ans+1 << endl;
        }
        else {
            cout << "impossible" << endl;
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 KB Output is correct
2 Incorrect 0 ms 340 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 340 KB Output is correct
2 Incorrect 0 ms 340 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 340 KB Output is correct
2 Incorrect 0 ms 340 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 73 ms 25256 KB Output is correct
2 Correct 75 ms 28340 KB Output is correct
3 Correct 88 ms 28312 KB Output is correct
4 Correct 88 ms 28808 KB Output is correct
5 Correct 123 ms 28764 KB Output is correct
6 Correct 116 ms 28484 KB Output is correct
7 Correct 129 ms 28544 KB Output is correct
8 Correct 99 ms 28588 KB Output is correct
9 Correct 49 ms 26628 KB Output is correct
10 Correct 79 ms 28076 KB Output is correct
11 Correct 74 ms 27884 KB Output is correct
12 Correct 74 ms 28148 KB Output is correct

Subtask #6
0 / 30.0

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