Submission #791724

#	Time	Username	Problem	Language	Result	Execution time	Memory
791724		math_rabbit_1028	Event Hopping (BOI22_events)	C++14	0 / 100	1576 ms	8296 KiB

events

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30