oj.uz

Submission #949673

# Submission time Handle Problem Language Result Execution time Memory
949673 2024-03-19T15:07:28 Z ifateen Event Hopping (BOI22_events) C++17
0 / 100
 404 ms 36232 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lc (node + 1)
#define mid ((tl + tr) >> 1)
#define rc (node + 2 * (mid - tl + 1))
const int MAXN = 1e5 + 5, MAX = 2e5 + 5;
pair<int, int> v[MAXN];
vector<int> ind, stop[MAXN];
int prv[22][MAXN]; // mn[i] = j such that l[j] is minimized and l[i]<=r[j]<=r[i]

struct Node {
    int mn = 1e18, mnIndex = -1;
    friend Node operator+(Node a, Node b) {
        if (a.mn < b.mn) return a;
        else return b;
    }
};

struct SegmentTree {
    vector<Node> tree;
    SegmentTree() {
        tree.resize(2 * MAX);
    }
    void update(int tl, int tr, int node, int val, int idx, int IDX) {
        if (tl == tr) tree[node] = tree[node] + Node{val, IDX};
        else {
            if (idx <= mid) update(tl, mid, lc, val, idx, IDX);
            else update(mid + 1, tr, rc, val, idx, IDX);
            tree[node] = tree[lc] + tree[rc];
        }
    }
    Node query(int tl, int tr, int node, int l, int r) {
        if (tl > r || tr < l) return {(int)1e18, -1};
        if (tl >= l && tr <= r) return tree[node];
        return query(tl, mid, lc, l, r) + query(mid + 1, tr, rc, l, r);
    }
};

signed main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i].first >> v[i].second;
        ind.push_back(v[i].first), ind.push_back(v[i].second);
    }
    sort(begin(ind), end(ind));
    ind.erase(unique(begin(ind), end(ind)), end(ind));
    for (int i = 1; i <= n; ++i) {
        v[i].first = lower_bound(begin(ind), end(ind), v[i].first) - begin(ind);
        v[i].second = lower_bound(begin(ind), end(ind), v[i].second) - begin(ind);
        stop[v[i].second].push_back(i);
    }
    SegmentTree st;
    for (auto & i : stop) {
        for (auto& idx : i) {
            prv[0][idx] = st.query(0, MAX - 1, 1, v[idx].first, v[idx].second).mnIndex;
            st.update(0, MAX - 1, 1, v[idx].first, v[idx].second, idx);
        }
    }
    for (int LOG = 1; LOG < 22; ++LOG) {
        for (int i = 1; i <= n; ++i) {
            int res = prv[LOG - 1][i];
            prv[LOG][i] = -1;
            if (res == -1) continue;
            prv[LOG][i] = prv[LOG - 1][res];
        }
    }
    while (q--) {
        int s, e;
        cin >> s >> e;
        int ans = 0;
        if (v[s].second > v[e].second) {
            cout << "impossible\n";
            continue;
        }
        if (s == e) {
            cout << "0\n";
            continue;
        }
        for (int i = 21; i >= 0; --i) {
            if (prv[i][e] == -1) continue;
            int S = v[prv[i][e]].first;
            if (S >= v[s].first) e = prv[i][e], ans += 1 << i;
        }
        if (v[e].first == v[s].first) cout << ans << '\n';
        else if (prv[0][e] != -1 && v[prv[0][e]].first <= v[s].first) cout << ans + 1 << '\n';
        else cout << "impossible\n";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27224 KB Output is correct
2 Correct 296 ms 35324 KB Output is correct
3 Correct 303 ms 36196 KB Output is correct
4 Correct 404 ms 36080 KB Output is correct
5 Runtime error 76 ms 15292 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 35768 KB Output is correct
2 Correct 295 ms 36232 KB Output is correct
3 Correct 384 ms 36228 KB Output is correct
4 Runtime error 73 ms 15296 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27224 KB Output is correct
2 Correct 296 ms 35324 KB Output is correct
3 Correct 303 ms 36196 KB Output is correct
4 Correct 404 ms 36080 KB Output is correct
5 Runtime error 76 ms 15292 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -