oj.uz

Submission #791956

# Submission time Handle Problem Language Result Execution time Memory
791956 2023-07-24T13:03:14 Z math_rabbit_1028 Event Hopping (BOI22_events) C++14
25 / 100
 136 ms 12500 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[2020202];

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 212 KB Output is correct
2 Correct 118 ms 12476 KB Output is correct
3 Correct 117 ms 12404 KB Output is correct
4 Correct 133 ms 12500 KB Output is correct
5 Runtime error 55 ms 7768 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 29 ms 1500 KB Output is correct
20 Correct 26 ms 1492 KB Output is correct
21 Correct 29 ms 1768 KB Output is correct
22 Correct 24 ms 1792 KB Output is correct
23 Correct 24 ms 1728 KB Output is correct
24 Correct 24 ms 1740 KB Output is correct
25 Correct 25 ms 1328 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 103 ms 11896 KB Output is correct
20 Correct 94 ms 11848 KB Output is correct
21 Correct 110 ms 11888 KB Output is correct
22 Runtime error 55 ms 10232 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 117 ms 12404 KB Output is correct
2 Correct 118 ms 12408 KB Output is correct
3 Correct 136 ms 12404 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 212 KB Output is correct
2 Correct 118 ms 12476 KB Output is correct
3 Correct 117 ms 12404 KB Output is correct
4 Correct 133 ms 12500 KB Output is correct
5 Runtime error 55 ms 7768 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -