oj.uz

Submission #791943

# Submission time Handle Problem Language Result Execution time Memory
791943 2023-07-24T12:44:18 Z math_rabbit_1028 Event Hopping (BOI22_events) C++14
0 / 100
 148 ms 12676 KB 
#include <bits/stdc++.h>
using namespace std;
#define st first
#define ed second

int n, q;
pair<int, int> event[101010];

vector<int> com;

struct node {
    int mn, idx;
} tree[808080];

node merger(node lt_val, node rt_val) {
    node ret;
    ret.mn = min(lt_val.mn, rt_val.mn);
    if (lt_val.mn == rt_val.mn) {
        ret.idx = (event[lt_val.idx].ed > event[rt_val.idx].ed ? lt_val.idx : rt_val.idx);
    }
    if (lt_val.mn < rt_val.mn) {
        ret.idx = lt_val.idx;
    }
    if (lt_val.mn > rt_val.mn) {
        ret.idx = rt_val.idx;
    }
    return ret;
}

void init(int v, int st, int ed) {
    if (st == ed) {
        tree[v].mn = 1e9;
        tree[v].idx = st;
        return;
    }
    int mid = (st + ed) / 2;
    init(2 * v, st, mid);
    init(2 * v + 1, mid + 1, ed);
    tree[v] = merger(tree[2 * v], tree[2 * v + 1]);
}

void update(int v, int st, int ed, int idx, int val, int i) {
    if (st == idx && ed == idx) {
        if (tree[v].mn > val) {
            tree[v].mn = val;
            tree[v].idx = i;
        }
        if (tree[v].mn == val && event[i].ed > event[tree[v].idx].ed) {
            tree[v].idx = i;
        }
        return;
    }
    if (st > idx || ed < idx) return;
    int mid = (st + ed) / 2;
    update(2 * v, st, mid, idx, val, i);
    update(2 * v + 1, mid + 1, ed, idx, val, i);
    tree[v] = merger(tree[2 * v], tree[2 * v + 1]);
}

node get(int v, int st, int ed, int lt, int rt) {
    if (lt > ed || rt < st) return {(int)1e9, 0};
    if (lt <= st && ed <= rt) return tree[v];
    int mid = (st + ed) / 2;
    return merger(
        get(2 * v, st, mid, lt, rt),
        get(2 * v + 1, mid + 1, ed, lt, rt)
    );
}

int sparse[101010][20];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> event[i].st >> event[i].ed;

    for (int i = 1; i <= n; i++) {
        com.push_back(event[i].st);
        com.push_back(event[i].ed);
    }
    sort(com.begin(), com.end());
    com.erase(unique(com.begin(), com.end()), com.end());
    for (int i = 1; i <= n; i++) {
        event[i].st = lower_bound(com.begin(), com.end(), event[i].st) - com.begin() + 1;
        event[i].ed = lower_bound(com.begin(), com.end(), event[i].ed) - com.begin() + 1;
        //cout << event[i].st << " " << event[i].ed << "\n";
    }

    init(1, 1, com.size());
    for (int i = 1; i <= n; i++) update(1, 1, com.size(), event[i].ed, event[i].st, i);
    for (int i = 1; i <= n; i++) {
        sparse[i][0] = get(1, 1, com.size(), event[i].st, event[i].ed).idx;
        assert(sparse[i][0] >= 1);
        //cout << sparse[i][0] << "\n";
    }
    for (int k = 1; k <= log2(n); k++) {
        for (int i = 1; i <= n; i++) {
            sparse[i][k] = sparse[sparse[i][k - 1]][k - 1];
        }
    }

    while (q--) {
        int s, e;
        cin >> s >> e;

        if (s == e) {
            cout << "0\n";
            continue;
        }

        int ans = 1;
        for (int k = log2(n); k >= 0; k--) {
            if (event[sparse[e][k]].st > event[s].st) {
                e = sparse[e][k];
                ans += (1 << k);
            }
        }
        if (event[sparse[e][0]].st < event[s].st || event[s].ed < event[sparse[e][0]].st) {
            cout << "impossible\n";
            continue;
        }
        if (event[e].st > event[s].ed) ans += 1;
        cout << ans << "\n";
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 125 ms 12640 KB Output is correct
3 Correct 131 ms 12548 KB Output is correct
4 Correct 138 ms 12548 KB Output is correct
5 Runtime error 51 ms 7908 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 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 476 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Incorrect 2 ms 480 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 12676 KB Output is correct
2 Correct 129 ms 12632 KB Output is correct
3 Correct 148 ms 12540 KB Output is correct
4 Runtime error 52 ms 8392 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 1 ms 340 KB Output is correct
2 Correct 125 ms 12640 KB Output is correct
3 Correct 131 ms 12548 KB Output is correct
4 Correct 138 ms 12548 KB Output is correct
5 Runtime error 51 ms 7908 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -