Submission #791979

#	Time	Username	Problem	Language	Result	Execution time	Memory
791979		math_rabbit_1028	Event Hopping (BOI22_events)	C++14	100 / 100	162 ms	18156 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 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 = 0;
        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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30