제출 #599128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
599128		alextodoran	Event Hopping (BOI22_events)	C++17	25 / 100	101 ms	66112 KiB

events

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
 
**/
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N_MAX = 100000;
const int BITS = 17;
 
int N, Q;
struct Event {
    int l, r;
};
bool operator < (const Event &e1, const Event &e2) {
    return make_pair(e1.r, e1.l) < make_pair(e2.r, e2.l);
}
Event events[N_MAX + 2];
int order[N_MAX + 2];
int id[N_MAX + 2];
 
struct SegTree {
    int left, right;
    int sum;
};
 
SegTree trees[N_MAX * 20];
int curr;
 
void build (int node, int l, int r) {
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    trees[node].left = ++curr;
    trees[node].right = ++curr;
    build(trees[node].left, l, mid);
    build(trees[node].right, mid + 1, r);
}
void build (int node) {
    build(node, 1, N);
}
 
int update (int node, int l, int r, int upos, int uval) {
    trees[++curr] = trees[node]; node = curr;
    if (l == r) {
        trees[node].sum += uval;
        return node;
    }
    int mid = (l + r) / 2;
    if (upos <= mid) {
        trees[node].left = update(trees[node].left, l, mid, upos, uval);
    } else {
        trees[node].right = update(trees[node].right, mid + 1, r, upos, uval);
    }
    trees[node].sum = trees[trees[node].left].sum + trees[trees[node].right].sum;
    return node;
}
int update (int node, int upos, int uval) {
    if (!(1 <= upos && upos <= N)) {
        return node;
    }
    return update(node, 1, N, upos, uval);
}
 
int query (int node, int l, int r, int qpos) {
    if (qpos <= l) {
        return trees[node].sum;
    }
    int mid = (l + r) / 2;
    if (qpos <= mid) {
        return query(trees[node].left, l, mid, qpos) + trees[trees[node].right].sum;
    } else {
        return query(trees[node].right, mid + 1, r, qpos);
    }
}
int query (int node, int qpos) {
    return query(node, 1, N, qpos);
}
 
int root[N_MAX + 2];
 
int rm[N_MAX + 2][BITS];
int lg2[N_MAX + 2];
void precalc () {
    for (int i = 1; i <= N; i++) {
        rm[i][0] = i;
        lg2[i] = lg2[i - 1];
        if ((1 << (lg2[i] + 1)) <= i) {
            lg2[i]++;
        }
    }
    for (int bit = 1; bit < BITS; bit++) {
        for (int i = 1; i + (1 << bit) - 1 <= N; i++) {
            int j = rm[i][bit - 1], k = rm[i + (1 << (bit - 1))][bit - 1];
            rm[i][bit] = (events[j].l <= events[k].l ? j : k);
        }
    }
}
int rmin (int l, int r) {
    int len = r - l + 1;
    int bit = lg2[len];
    int j = rm[l][bit];
    int k = rm[r - (1 << bit) + 1][bit];
    return (events[j].l <= events[k].l ? j : k);
}
 
int minl[N_MAX + 2];
 
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        cin >> events[i].l >> events[i].r;
    }
    iota(order + 1, order + N + 1, 1);
    sort(order + 1, order + N + 1, [&] (const int &i, const int &j) {
        return events[i] < events[j];
    });
    for (int i = 1; i <= N; i++) {
        id[order[i]] = i;
    }
    sort(events + 1, events + N + 1);
    precalc();
 
    root[0] = ++curr;
    build(root[0]);
    for (int i = 1; i <= N; i++) {
        int l = 1, r = i;
        while (l < r) {
            int mid = (l + r) / 2;
            if (events[i].l <= events[mid].r) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        int j;
        if (l == i) {
            j = 0;
            minl[i] = i;
        } else {
            j = rmin(l, i - 1);
            minl[i] = minl[j];
        }
        root[i] = root[j];
        root[i] = update(root[i], i - 1, +1);
        root[i] = update(root[i], j - 1, -1);
        root[i] = update(root[i], l - 1, +1);
    }
 
    while (Q--) {
        int i, j;
        cin >> i >> j;
        i = id[i]; j = id[j];
        if (i == j) {
            cout << 0 << "\n";
        } else if (events[i].r == events[j].r) {
            cout << 1 << "\n";
        } else if (minl[j] <= i && i < j) {
            cout << query(root[j], i) << "\n";
        } else {
            cout << "impossible\n";
        }
    }
 
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30