oj.uz

Submission #589411

# Submission time Handle Problem Language Result Execution time Memory
589411 2022-07-04T15:49:28 Z 1zaid1 Event Hopping (BOI22_events) C++17
25 / 100
 1500 ms 9848 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int M = 1e5+2;
int N = exp2(ceil(log2(M)));
struct rng {int l=INT_MAX, r, i;};
int nxt[M], L, R;

rng seg[4*M];

rng comb(rng a, rng b) {
    if (a.l < b.l) return a;
    return b;
}

void update(int ind) {
    while (ind /= 2) seg[ind] = comb(seg[ind*2], seg[ind*2+1]);
}

rng query(int l = 1, int r = N, int ind = 1) {
    if (l > R || r < L) return {INT_MAX, 0, 0};
    if (L <= l && r <= R) return seg[ind];
    return comb(query(l, (l+r)/2, ind*2), query((l+r)/2+1, r, ind*2+1));
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    cin >> n >> q;

    vector<int> rs;
    vector<rng> v(n), cp;
    for (auto &[l, r, i]:v) cin >> l >> r;
    for (int i = 0; i < n; i++) v[i].i = i;
    cp = v;
    sort(cp.begin(), cp.end(), [](rng a, rng b){return a.r < b.r;});
    
    for (int i = 0; i < n; i++) {
        rs.push_back(cp[i].r);

        seg[i+N] = cp[i];
        update(N+i);
    }

    for (auto [l, r, i]:v) {
        nxt[i] = i;
        L = lower_bound(rs.begin(), rs.end(), l)-rs.begin()+1;
        R = upper_bound(rs.begin(), rs.end(), r)-rs.begin();
        if (!R) continue;
        auto tmp = query();
        if (tmp.l < l) nxt[i] = tmp.i;
    }

    bitset<100005> vis;
    while (q--) {
        int a, b;
        cin >> a >> b; a--; b--;
        if (a == b) {
            cout << 0 << endl;
            continue;
        }

        int ans = 1;
        auto tmp = v[b];
        while (v[a].r < tmp.l) {
            if (nxt[tmp.i] == tmp.i) break;
            tmp = v[nxt[tmp.i]];
            ans++;
        }

        if (tmp.l <= v[a].r && v[a].r <= tmp.r) {
            cout << ans << endl;
        } else {
            cout << "impossible" << endl;
        }
    }

    return 0;
}
/*
8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8

5 2
1 3
2 4
4 7
7 9
3 7
1 4
3 2

y = 5 \left\{1 < x < 3\right\}
y = 4 \left\{2 < x < 4\right\}
y = 3 \left\{4 < x < 7\right\}
y = 2 \left\{7 < x < 9\right\}
y = 1 \left\{3 < x < 7\right\}

*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 1587 ms 8280 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5052 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5048 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5052 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5048 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 5 ms 5024 KB Output is correct
15 Correct 3 ms 5048 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5160 KB Output is correct
19 Correct 1425 ms 5968 KB Output is correct
20 Execution timed out 1566 ms 6004 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5052 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5048 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4980 KB Output is correct
12 Correct 4 ms 5040 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 5060 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 4 ms 5040 KB Output is correct
18 Correct 3 ms 5048 KB Output is correct
19 Correct 336 ms 9848 KB Output is correct
20 Correct 129 ms 8620 KB Output is correct
21 Correct 113 ms 8668 KB Output is correct
22 Correct 93 ms 8464 KB Output is correct
23 Correct 71 ms 8776 KB Output is correct
24 Correct 94 ms 9080 KB Output is correct
25 Correct 50 ms 8372 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1590 ms 8276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 1587 ms 8280 KB Time limit exceeded
3 Halted 0 ms 0 KB -