Submission #1187490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187490		qwusha	Event Hopping (BOI22_events)	C++20	0 / 100	315 ms	44944 KiB

events

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e15;

int n;

vector<int> dtl;
vector<vector<int>> gl;
vector<int> col;
int curco = 0;

void dfsl(int v, int p = -1, int d=0) {
    dtl[v] = d;
    for (auto u : gl[v]) {
        if (u != p) {
            dfsl(u, v, d + 1);
        }
    }
}



bool cmp(vector<int> a, vector<int> b) {
    if (a[1] == b[1]) {
        return a[0] < b[0];
    }
    return (a[1] < b[1]);
}


vector<vector<int>> b;

struct segtree{
    int sz = 1;
    vector<pair<int, int>> tree;
    void init() {
        while (sz < n) {
            sz <<= 1;
        }
        tree.resize(sz * 2 - 1, {inf, inf});
        build(0,0,sz);
    }
    void build(int v, int l, int r) {
        if (r - l == 1) {
            if (l < n) {
                tree[v] = {b[l][0], b[l][2]};
            }
            return;
        }
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
        tree[v] = min(tree[v * 2 + 1], tree[v * 2 + 2]);
    }
    pair<int, int> answer(int lq, int rq) {
        return ans(0,0,sz,lq,rq);
    }
    pair<int, int> ans(int v, int l, int r, int lq, int rq) {
        if (lq <= l && r <= rq) {
            return tree[v];
        }
        if (lq >= r || rq <= l) {
            return {inf, inf};
        }
        int m = (l + r) / 2;
        auto a1 = ans(v * 2 + 1, l, m, lq, rq),
        a2 = ans(v * 2 + 2, m, r, lq, rq);
        return min(a1, a2);
    }
};


signed main() {
    int  q;
    cin >> n >> q;
    gl.resize(n);
    dtl.resize(n);
    col.resize(n);
    vector<vector<int>> a(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
        a[i][2] = i;
    }
    b = a;
    auto ini = a;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end(), cmp);
    vector<int> coolle;

    segtree tree;
    tree.init();
    vector<int> par_to_lef(n);
    for (int i = 0; i < n; i++) {
        par_to_lef[i] = i;
    }
    for (int i = n - 1; i >= 0; i--) {
        int ind = b[i][2];
        int beg = b[i][0];
        int end = b[i][1];
        int l = -1, r = n - 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (b[mid][1] >= beg) {
                r = mid;
            } else {
                l = mid;
            }
        }
        auto re = tree.answer(r, ind + 1);
        if (re.fi < beg) {
            par_to_lef[ind] = re.se;
            gl[ind].push_back(re.se);
            gl[re.se].push_back(ind);
        } else {
            coolle.push_back(ind);
        }
    }
    curco = 0;
    for (auto el : coolle) {
        dfsl(el);
    }
    int logn = 3, vallog = 1;
    while (vallog < n) {
        vallog *= 2;
        logn++;
    }
    vector<vector<int>> upstl(logn, vector<int>(n));
    for (int i = 0; i < n; i++) {
        upstl[0][i] = par_to_lef[i];
    }
    for (int j = 1; j < logn; j++) {
        for (int i = 0; i < n; i++) {
            upstl[j][i] = upstl[j - 1][upstl[j - 1][i]];
        }
    }
    for (int qw = 0; qw < q; qw++) {
        int s, e;
        cin >> s >> e;
        s--;
        e--;
        int curu = e;
        for (int i = logn - 1; i >= 0; i--) {
            if (ini[upstl[i][curu]][0] > ini[s][0])
                curu = upstl[i][curu];
        }
        if (ini[s][1] > ini[curu][1]) {
            cout << "impossible" << '\n';
        } else if (s == e) {
            cout << 0 << '\n';
        } else {
            curu = par_to_lef[curu];
            if (curu == s) {
                cout << dtl[e] - dtl[curu] << '\n';
            } else if (ini[curu][0] <= ini[s][0]) {
                cout << 1 + dtl[e] - dtl[curu] << '\n';
            } else {
                cout << "impossible" << '\n';
            }
        }
    }
}

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