oj.uz

Submission #1026546

# Submission time Handle Problem Language Result Execution time Memory
1026546 2024-07-18T07:54:13 Z gyg Event Hopping (BOI22_events) C++17
20 / 100
 211 ms 31100 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;

    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];
        
        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 << "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++;

            if (j == 0) { cout << "impossible" << '\n'; continue; }
            assert(r[j] >= r[f]);
            cout << ans << '\n';
        }
    }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 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 2396 KB Output is correct
2 Incorrect 1 ms 2396 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 2396 KB Output is correct
2 Incorrect 1 ms 2396 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 2396 KB Output is correct
2 Incorrect 1 ms 2396 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 118 ms 19140 KB Output is correct
2 Correct 115 ms 19140 KB Output is correct
3 Correct 127 ms 22180 KB Output is correct
4 Correct 158 ms 30212 KB Output is correct
5 Correct 129 ms 22544 KB Output is correct
6 Correct 193 ms 30844 KB Output is correct
7 Correct 190 ms 30904 KB Output is correct
8 Correct 211 ms 31100 KB Output is correct
9 Correct 164 ms 28940 KB Output is correct
10 Correct 188 ms 30380 KB Output is correct
11 Correct 188 ms 30368 KB Output is correct
12 Correct 190 ms 30536 KB Output is correct

Subtask #6
0 / 30.0

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