oj.uz

Submission #791954

# Submission time Handle Problem Language Result Execution time Memory
791954 2023-07-24T13:01:58 Z math_rabbit_1028 Event Hopping (BOI22_events) C++14
25 / 100
 162 ms 13836 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;
        //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 = 0;
        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[e].st <= event[s].ed && event[s].ed <= event[e].ed) ans += 1;
        else {
            e = sparse[e][0]; ans += 1;
            if (event[e].st <= event[s].ed && event[s].ed <= event[e].ed) ans += 1;
            else {
                cout << "impossible\n";
                continue;
            }
        }
        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 136 ms 12420 KB Output is correct
3 Correct 132 ms 12400 KB Output is correct
4 Correct 154 ms 12412 KB Output is correct
5 Runtime error 65 ms 7852 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 480 KB Output is correct
16 Correct 1 ms 484 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 30 ms 2388 KB Output is correct
20 Correct 35 ms 2512 KB Output is correct
21 Correct 29 ms 2644 KB Output is correct
22 Correct 25 ms 2824 KB Output is correct
23 Correct 25 ms 2788 KB Output is correct
24 Correct 25 ms 2764 KB Output is correct
25 Correct 26 ms 2424 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 480 KB Output is correct
15 Correct 1 ms 480 KB Output is correct
16 Correct 1 ms 476 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 118 ms 13836 KB Output is correct
20 Correct 107 ms 13052 KB Output is correct
21 Correct 107 ms 13768 KB Output is correct
22 Runtime error 53 ms 12176 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 12404 KB Output is correct
2 Correct 126 ms 12420 KB Output is correct
3 Correct 162 ms 12428 KB Output is correct
4 Runtime error 52 ms 8304 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 136 ms 12420 KB Output is correct
3 Correct 132 ms 12400 KB Output is correct
4 Correct 154 ms 12412 KB Output is correct
5 Runtime error 65 ms 7852 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -