Submission #746009

#	Time	Username	Problem	Language	Result	Execution time	Memory
746009		vjudge1	Event Hopping (BOI22_events)	C++17	100 / 100	245 ms	50524 KiB

events

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 1e5;
const int maxwidth = 2 * maxn;
const int inf = maxwidth + 1;
const int logn = 20;

void print_impossible() {
    cout << "impossible\n";
    return;
}

struct interval {
    int l, r, id;
    bool operator < (const interval & other) const {
        return l < other.l;
    }
};

const interval def = {inf, inf, 0};

vector<interval> v;
interval arr[1 + maxwidth];
interval tree[1 + 4 * maxwidth];

void reset() {
    for(int i = 0; i <= maxwidth; i++) {
        arr[i] = def;
    }
    for(int i = 0; i <= 4 * maxwidth; i++) {
        tree[i] = def;
    }
}

void build(int v, int vl, int vr) {
    // cout << v << " " << vl << " " << vr << endl;
    if(vl == vr) {
        tree[v] = arr[vl];
        return;
    }
    int mid = (vl + vr) / 2;
    build(2 * v, vl, mid);
    build(2 * v  + 1, mid + 1, vr);
    tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}

interval query(int v, int vl, int vr, int ql, int qr) {
    if(vr < ql || vl > qr) {
        return def;
    }
    if(vl == ql && vr == qr) {
        return tree[v];
    }
    int mid = (vl + vr) / 2;
    return min(query(2 * v, vl, mid, ql, min(qr, mid)), query(2 * v + 1, mid + 1, vr, max(ql, mid + 1), qr));
}

int n, q;
vector<pii > queries;
int par[1 + maxn];
int lift[1 + maxn][logn];

void compress() {
    vector<int> comp;
    for(const interval &cur : v) {
        comp.pb(cur.l), comp.pb(cur.r);
    }
    sort(comp.begin(), comp.end());
    comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    for(interval &cur : v) {
        cur.l = (lower_bound(comp.begin(), comp.end(), cur.l) - comp.begin()) + 1;
        cur.r = (lower_bound(comp.begin(), comp.end(), cur.r) - comp.begin()) + 1;
    }
    return;
}

bool can_step(const interval &a, const interval &b) {
    return (b.l <= a.r && a.r <= b.r);
}

int ans_query(int s, int e) {
    if(s == e) {
        return 0;
    }
    interval si = v[s - 1], ei = v[e - 1];
    if(si.r > ei.r) {
        return -1;
    }
    if(can_step(si, ei)) {
        return 1;
    }
    int cur = e, cnt = 0;
    for(int j = logn - 1; j >= 0; j--) {
        int possible_new_candidate_option = lift[cur][j];
        if(possible_new_candidate_option == 0) {
            continue;
        }
        interval other = v[possible_new_candidate_option - 1];
        if(other.l > si.r) {
            cur = possible_new_candidate_option;
            cnt += (1 << j);
        }
    }
    cur = par[cur];
    cnt++;
    if(!can_step(si, v[cur - 1])) {
        return -1;
    }
    cnt++;
    return cnt;
}

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        v.pb({l, r, i});
    }
    for(int i = 1; i <= q; i++) {
        int s, e;
        cin >> s >> e;
        queries.pb({s, e});
    }
    compress();
    reset();
    for(const interval &cur : v) {
        arr[cur.r] = min(arr[cur.r], cur);
    }
    /*for(const interval &cur : v) {
        cout << cur.l << " " << cur.r << " " << cur.id << endl;
    }*/
    build(1, 1, maxwidth);
    //cout << "here" << endl;
    for(const interval &cur : v) {
        par[cur.id] = query(1, 1, maxwidth, cur.l, cur.r).id;
    }
    /*for(int i = 1; i <= n; i++) {
        cout << par[i] << " ";
    }
    cout << endl;*/
    for(int i = 1; i <= n; i++) {
        lift[i][0] = par[i];
    }
    for(int j = 1; j < logn; j++) {
        for(int i = 1; i <= n; i++) {
            lift[i][j] = lift[lift[i][j - 1]][j - 1];
        }
    }
    for(const pii &p : queries) {
        int s = p.fi, e = p.se;
        int res = ans_query(s, e);
        if(res == -1) {
            print_impossible();
        } else {
            cout << res << "\n";
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    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