oj.uz

Submission #1026570

# Submission time Handle Problem Language Result Execution time Memory
1026570 2024-07-18T08:08:33 Z gyg Event Hopping (BOI22_events) C++17
10 / 100
 207 ms 40576 KB 
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>    
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 1e5 + 5, INF = 1e9, MAX_Q = 1e5 + 5;

int n, q;
array<int, MAX_N> l, r;
unordered_map<int, vector<int>> at_r;

int n_ccs;
unordered_map<int, int> cc;

array<pii, 8 * MAX_N> st; // {r[i], i}
void update(int l, int r, pii x, int u = 1, int lo = 1, int hi = n_ccs) {
    if (l <= lo && hi <= r) { st[u] = max(st[u], x); return; }
    int mid = (lo + hi) / 2;
    if (l <= mid) update(l, r, x, 2 * u, lo, mid); 
    if (r > mid) update(l, r, x, 2 * u + 1, mid + 1, hi);
}
pii query(int i, int u = 1, int lo = 1, int hi = n_ccs) {
    if (lo == hi) return st[u];
    int mid = (lo + hi) / 2;
    if (i <= mid) return max(st[u], query(i, 2 * u, lo, mid));
    else return max(st[u], query(i, 2 * u + 1, mid + 1, hi));
}

array<array<int, 20>, MAX_N> anc;
void precomp() {
    set<int> coords;
    for (int i = 1; i <= n; i++) coords.insert(l[i]), coords.insert(r[i]);
    while (coords.size()) {
        n_ccs++, cc[*coords.begin()] = n_ccs;
        coords.erase(coords.begin());
    }

    for (int i = 1; i <= n; i++) update(cc[l[i]], cc[r[i]], {r[i], i});
    for (int i = 1; i <= n; i++) {
        pii x = query(cc[r[i]]);
        if (x == make_pair(r[i], i)) continue;
        anc[i][0] = x.second;
        // cout << i << ": " << x.second << endl;
    }

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

int main() {
    // freopen("event.in", "r", stdin);
    cin.sync_with_stdio(false), cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        at_r[r[i]].push_back(i);
    } 
    
    precomp();

    for (int i = 1; i <= q; i++) {
        int s, f; cin >> s >> f;
        if (s == f) { cout << 0 << '\n'; continue; }
        if (r[s] == r[f]) { cout << 1 << '\n'; continue;}
        if (r[s] > r[f]) { cout << "impossible" << '\n'; continue; }

        int j = s, ans = 0;
        for (int k = 19; k >= 0; k--)
            if (anc[j][k] != 0 && r[anc[j][k]] < r[f])
                j = anc[j][k], ans += (1 << k);
        assert(r[j] < r[f]);
        j = anc[j][0], ans++;
        assert(j == 0 || r[j] >= r[f]);

        if (r[j] == r[f] && j != f) ans++;
        else if (j != f) { cout << "impossible" << '\n'; continue; }
        
        cout << ans << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 131 ms 31436 KB Output is correct
3 Correct 135 ms 31188 KB Output is correct
4 Correct 156 ms 32540 KB Output is correct
5 Correct 149 ms 33568 KB Output is correct
6 Correct 155 ms 33988 KB Output is correct
7 Correct 170 ms 33988 KB Output is correct
8 Correct 196 ms 40576 KB Output is correct
9 Correct 173 ms 40576 KB Output is correct
10 Correct 158 ms 33072 KB Output is correct
11 Correct 172 ms 37316 KB Output is correct
12 Correct 80 ms 26724 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Incorrect 1 ms 2652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Incorrect 1 ms 2652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Incorrect 1 ms 2652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 31544 KB Output is correct
2 Correct 138 ms 31240 KB Output is correct
3 Correct 148 ms 31168 KB Output is correct
4 Correct 184 ms 39300 KB Output is correct
5 Correct 155 ms 31680 KB Output is correct
6 Incorrect 207 ms 40364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 131 ms 31436 KB Output is correct
3 Correct 135 ms 31188 KB Output is correct
4 Correct 156 ms 32540 KB Output is correct
5 Correct 149 ms 33568 KB Output is correct
6 Correct 155 ms 33988 KB Output is correct
7 Correct 170 ms 33988 KB Output is correct
8 Correct 196 ms 40576 KB Output is correct
9 Correct 173 ms 40576 KB Output is correct
10 Correct 158 ms 33072 KB Output is correct
11 Correct 172 ms 37316 KB Output is correct
12 Correct 80 ms 26724 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Incorrect 1 ms 2652 KB Output isn't correct
18 Halted 0 ms 0 KB -