Submission #698118

#	Time	Username	Problem	Language	Result	Execution time	Memory
698118		Duy_e	Event Hopping (BOI22_events)	C++14	10 / 100	219 ms	26812 KiB

events

#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define nd second
#define st first
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;
const long long N = 2e5 + 5;
const long long INF = 2e9;
int f[N], n, q, pos[N], ans[N];
vector <int> st;
vector <int> in[N], queries[N];

struct events {
    int s, e, id;
    bool operator <(events other) {
        if (e == other.e) return s < other.s;
        return e < other.e;
    }
} a[N];

struct query {
    int u, v, id;
} qr[N];

namespace seg_assign {
    int n, st[4 * N];

    void init(int _n) {
        n = _n;
        memset(st, -1, sizeof st);
    }

    void push(int id) {
        if (st[id] == -1) return;
        st[id << 1] = st[id << 1 | 1] = st[id];
        st[id] = -1;
    }

    void upd(int id, int l, int r, int lef, int rig, int v) {
        if (l > rig || r < lef) return;
        if (lef <= l && r <= rig) {
            st[id] = v;
            return;
        }
        push(id);
        int mid = (l + r) >> 1;
        upd(id << 1, l, mid, lef, rig, v);
        upd(id << 1 | 1, mid + 1, r, lef, rig, v);
    }

    void upd(int l, int r, int v) {
        upd(1, 1, n, l, r, v);
    }

    int get(int id, int l, int r, int i) {
        if (l == r) return st[id];
        push(id);
        int mid = (l + r) >> 1;
        if (mid >= i) return get(id << 1, l, mid, i);
        return get(id << 1 | 1, mid + 1, r, i);
    }

    int get(int i) {
        return get(1, 1, n, i);
    }
}

namespace seg_min {
    int n, st[4 * N];

    void init(int _n) {
        n = _n;
        rep(i, 0, 4 * N - 1) st[i] = INF;
    }

    void upd(int id, int l, int r, int i, int v) {
        if (l > i || r < i) return;
        if (l == r) {
            st[id] = min(st[id], v);
            return;
        }

        int mid = (l + r) >> 1;
        upd(id << 1, l, mid, i, v); upd(id << 1 | 1, mid + 1, r, i, v);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }

    void upd(int i, int v) {
        upd(1, 1, n, i, v);
    }

    int get(int id, int l, int r, int lef, int rig) {
        if (l > rig || r < lef) return INF;
        if (lef <= l && r <= rig) return st[id];
        int mid = (l + r) >> 1;
        return min(
            get(id << 1, l, mid, lef, rig),
            get(id << 1 | 1, mid + 1, r, lef, rig)
        );
    }

    int get(int l, int r) {
        return get(1, 1, n, l, r);
    }
}

vector <int> cmp;

void read() {
    cin >> n >> q;
    rep(i, 1, n) {
        cin >> a[i].s >> a[i].e;
        a[i].id = i;
        cmp.push_back(a[i].s);
        cmp.push_back(a[i].e);
    }

    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());

    auto find = [&](int x) {
        return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin() + 1;
    };

    rep(i, 1, n) {
        a[i].s = find(a[i].s);
        a[i].e = find(a[i].e);
    }
}

void solve() {
    rep(i, 1, n) {
        in[a[i].e].push_back(i);

    }
    rep(i, 1, q) {
        ans[i] = INF;
        cin >> qr[i].u >> qr[i].v;
        if (a[qr[i].u].e > a[qr[i].v].e) continue;
        if (qr[i].u == qr[i].v)
            ans[i] = 0;
        else
            queries[qr[i].v].push_back(i);
    }

    auto cmp = [&](int i, int j) {
        return a[i].s > a[j].s;
    };

    seg_min :: init(2 * n);
    seg_assign :: init(2 * n);

    //rep(i, 1, n) seg_min :: upd(a[i].e, a[i].s);
    rep(i, 1, 2 * n) {
        sort(in[i].begin(), in[i].end(), cmp);

//in[i] luu chi so nhung con ket thuc tai i
        for (int id: in[i]) {
            while ((st.size() && a[st.back()].s >= a[id].s) ||
                   (st.size() > 1 && a[st[st.size() - 2]].e >= a[id].s)) {
                int j = st.back();
                st.pop_back();
                seg_assign :: upd(a[j].s, a[j].e, (int)st.size());
            }

            st.push_back(id);
            seg_min :: upd(a[id].e, a[id].s);
            f[i] = seg_min :: get(a[id].s, a[id].e);
            seg_min :: upd(i, f[i]);
            seg_assign :: upd(a[id].s, a[id].e, (int)st.size());

            int v = id;
            for (int j: queries[v]) {
                int u = qr[j].u;
                if (f[i] > a[u].e) continue;
                int tmp = seg_assign :: get(a[u].e);
                ans[j] = min(ans[j], (int)st.size() - tmp + 1);
            }
        }

        for (int id: in[i]) for (int j: queries[id]) {
            int u = qr[j].u;
            if (f[i] > a[u].e) continue;
            int tmp = seg_assign :: get(a[u].e);
            ans[j] = min(ans[j], (int)st.size() - tmp + 2);
        }
    }

    rep(i, 1, q) {
        if (ans[i] >= INF)
            cout << "impossible\n";
        else
            cout << ans[i] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

//    freopen("events.inp", "r", stdin);
//    freopen("events.out", "w", stdout);

    read();
    solve();
    return 0;
}


/*

sort(events)
f[u] = min range current activating
query index of range -> [f[i], i]

query get ans
delete range -> set <pii> ? stack ? vector ? deque -> stack

f[u] ? min f[i], i belong to [su, eu]

everytime pop one element from stack -> upd index? ->
-> assign with stack size -> get = stack size - ans = index
get ans = fens

45m
*/

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