oj.uz

Submission #949727

# Submission time Handle Problem Language Result Execution time Memory
949727 2024-03-19T15:28:40 Z ifateen Event Hopping (BOI22_events) C++17
20 / 100
 154 ms 37828 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[MAX];
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() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
    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 (s == e) 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 29276 KB Output is correct
2 Correct 113 ms 37576 KB Output is correct
3 Correct 116 ms 37060 KB Output is correct
4 Correct 150 ms 37060 KB Output is correct
5 Incorrect 117 ms 37436 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29276 KB Output is correct
2 Correct 5 ms 29276 KB Output is correct
3 Correct 6 ms 29276 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 6 ms 29152 KB Output is correct
6 Incorrect 6 ms 29276 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 29276 KB Output is correct
2 Correct 5 ms 29276 KB Output is correct
3 Correct 6 ms 29276 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 6 ms 29152 KB Output is correct
6 Incorrect 6 ms 29276 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 29276 KB Output is correct
2 Correct 5 ms 29276 KB Output is correct
3 Correct 6 ms 29276 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 6 ms 29152 KB Output is correct
6 Incorrect 6 ms 29276 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 37332 KB Output is correct
2 Correct 119 ms 37300 KB Output is correct
3 Correct 154 ms 37132 KB Output is correct
4 Correct 105 ms 37828 KB Output is correct
5 Correct 148 ms 37572 KB Output is correct
6 Correct 139 ms 37212 KB Output is correct
7 Correct 147 ms 37248 KB Output is correct
8 Correct 145 ms 37572 KB Output is correct
9 Correct 96 ms 36092 KB Output is correct
10 Correct 139 ms 36880 KB Output is correct
11 Correct 124 ms 36804 KB Output is correct
12 Correct 124 ms 36904 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29276 KB Output is correct
2 Correct 113 ms 37576 KB Output is correct
3 Correct 116 ms 37060 KB Output is correct
4 Correct 150 ms 37060 KB Output is correct
5 Incorrect 117 ms 37436 KB Output isn't correct
6 Halted 0 ms 0 KB -