oj.uz

Submission #791724

# Submission time Handle Problem Language Result Execution time Memory
791724 2023-07-24T09:07:25 Z math_rabbit_1028 Event Hopping (BOI22_events) C++14
0 / 100
 1500 ms 8296 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 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++) {
        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].st, event[i].ed - 1, event[i].ed);

    while (q--) {
        int s, e;
        cin >> s >> 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.st << " " << can.ed << "\n";
            if (!(event[e].st > can.ed || event[e].ed < can.st)) {
                cout << cnt << "\n";
                break;
            }
            node prev = get(1, 1, com.size(), can.st, can.ed);
            if (prev.mn == can.st && prev.mx == can.ed) {
                cout << "impossible\n";
                break;
            }
            can.st = prev.mn;
            can.ed = 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 1576 ms 8296 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 1 ms 212 KB Output is correct
3 Correct 17 ms 340 KB Output is correct
4 Correct 4 ms 408 KB Output is correct
5 Incorrect 5 ms 336 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 1 ms 212 KB Output is correct
3 Correct 17 ms 340 KB Output is correct
4 Correct 4 ms 408 KB Output is correct
5 Incorrect 5 ms 336 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 1 ms 212 KB Output is correct
3 Correct 17 ms 340 KB Output is correct
4 Correct 4 ms 408 KB Output is correct
5 Incorrect 5 ms 336 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 1562 ms 8288 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 1576 ms 8296 KB Time limit exceeded
3 Halted 0 ms 0 KB -