oj.uz

Submission #791807

# Submission time Handle Problem Language Result Execution time Memory
791807 2023-07-24T10:17:21 Z math_rabbit_1028 Event Hopping (BOI22_events) C++14
0 / 100
 1500 ms 7704 KB 
#include <bits/stdc++.h>
using namespace std;

int n, q;
struct events {
    int st, ed;
    int idx;
} event[101010];
bool compare(events p, events q) {
    if (p.ed == q.ed) return p.st < q.st;
    return p.ed < q.ed;
}

int reord[101010];
vector<int> com;

struct node {
    int mx, mn, mxlazy, mnlazy;
} tree[808080];

node merger(node lt_val, node rt_val) {
    node ret;
    ret.mx = max(lt_val.mx, rt_val.mx);
    ret.mn = min(lt_val.mn, rt_val.mn);
    ret.mxlazy = 0;
    ret.mnlazy = 1e9;
    return ret;
}

void propagation(int v, int st, int ed) {
    tree[v].mx = max(tree[v].mx, tree[v].mxlazy);
    tree[v].mn = min(tree[v].mn, tree[v].mnlazy);
    if (st != ed) {
        tree[2 * v].mxlazy = max(tree[2 * v].mxlazy, tree[v].mxlazy);
        tree[2 * v].mnlazy = min(tree[2 * v].mnlazy, tree[v].mnlazy);
        tree[2 * v + 1].mxlazy = max(tree[2 * v + 1].mxlazy, tree[v].mxlazy);
        tree[2 * v + 1].mnlazy = min(tree[2 * v + 1].mnlazy, tree[v].mnlazy);
    }
    tree[v].mxlazy = 0;
    tree[v].mnlazy = 1e9;
}

void init(int v, int st, int ed) {
    if (st == ed) {
        tree[v].mx = 0;
        tree[v].mn = 1e9;
        tree[v].mxlazy = 0;
        tree[v].mnlazy = 1e9;
        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 lt, int rt, int val) {
    propagation(v, st, ed);
    if (lt > ed || rt < st) return;
    if (lt <= st && ed <= rt) {
        tree[v].mxlazy = val;
        tree[v].mnlazy = val;
        propagation(v, st, ed);
        return;
    }
    int mid = (st + ed) / 2;
    update(2 * v, st, mid, lt, rt, val);
    update(2 * v + 1, mid + 1, ed, lt, rt, val);
    tree[v] = merger(tree[2 * v], tree[2 * v + 1]);
}

node get(int v, int st, int ed, int lt, int rt) {
    propagation(v, st, ed);
    if (lt > ed || rt < st) return {0, (int)1e9, 0, (int)1e9};
    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 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++) event[i].idx = i;
    sort(event + 1, event + n + 1, compare);
    for (int i = 1; i <= n; i++) reord[event[i].idx] = i;

    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;
    }

    init(1, 1, com.size());
    for (int i = 1; i <= n; i++) update(1, 1, com.size(), event[i].st, event[i].ed - 1, event[i].ed);

    while (q--) {
        int s, e;
        cin >> s >> e;
        s = reord[s];
        e = reord[e];

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

        int cnt = 1;
        pair<int, int> can = {event[s].ed, event[s].ed};
        while (true) {
            //cout << can.first << " " << can.second << "\n";
            if (!(event[e].st > can.second || event[e].ed < can.first)) {
                cout << cnt << "\n";
                break;
            }
            node prev = get(1, 1, com.size(), can.first, can.second);
            if (prev.mn == can.first && prev.mx == can.second) {
                cout << "impossible\n";
                break;
            }
            can.first = prev.mn;
            can.second = prev.mx;
            cnt++;
        }
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1555 ms 7628 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 17 ms 348 KB Output is correct
4 Correct 5 ms 424 KB Output is correct
5 Incorrect 4 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 17 ms 348 KB Output is correct
4 Correct 5 ms 424 KB Output is correct
5 Incorrect 4 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 17 ms 348 KB Output is correct
4 Correct 5 ms 424 KB Output is correct
5 Incorrect 4 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1567 ms 7704 KB Time limit exceeded
2 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 Execution timed out 1555 ms 7628 KB Time limit exceeded
3 Halted 0 ms 0 KB -