Submission #1187314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187314		qwusha	Event Hopping (BOI22_events)	C++20	30 / 100	590 ms	101172 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, dtr;
vector<vector<int>> gl;
vector<set<vector<int>>> gr;
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);
        }
    }
}
void dfsr(int v, int p = -1, int d=0) {
    col[v] = curco;
    dtr[v] = d;
    for (auto u : gr[v]) {
        if (u[2] != p) {
            dfsr(u[2], 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]);
}

signed main() {
    int  q;
    cin >> n >> q;
    gl.resize(n);
    gr.resize(n);
    dtr.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;
    }
    auto b = a;
    auto ini = a;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end(), cmp);
    vector<int> coolle, coolri;
    vector<vector<int>> to_rig;

    int last = -1;
    int cur = 0;
    while (cur < n) {
        int val = a[cur][0];
        int maxi = -1;
        int mind = -1;
        while(cur < n && a[cur][0] == val) {
            if (maxi < a[cur][1]) {
                maxi = a[cur][1];
                mind= cur;
            }
            cur++;
        }
        if (maxi > last) {
            to_rig.push_back(a[mind]);
            last = maxi;
        }
    }
    vector<pair<int, int>> suf(n + 1);
    suf[n] = {inf, inf};
    for (int i = n - 1; i >= 0; i--) {
        pair<int, int> pa = {b[i][0], b[i][2]};
        suf[i] = min(suf[i + 1], pa);
    }
    vector<int> par_to_lef(n), par_to_rig(n);
    for (int i = 0; i < n; i++) {
        par_to_lef[i] = i;
        par_to_rig[i] = i;
    }
    for (int i = 0; i < n; i++) {
        int ind = a[i][2];
        int end = a[i][1];
        int l = 0, r = to_rig.size();
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (to_rig[mid][0] <= end) {
                l = mid;
            } else {
                r = mid;
            }
        }
        if (to_rig[l][2] == ind) {
            coolri.push_back(ind);
        } else {
            int pare = to_rig[l][2];
            par_to_rig[ind] = pare;
            gr[ind].insert(ini[pare]);
            gr[pare].insert(ini[ind]);
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        int ind = b[i][2];
        int beg = b[i][0];
        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 pa = suf[r];
        if (pa.fi < beg) {
            gl[ind].push_back(pa.se);
            gl[pa.se].push_back(ind);
        }
    }
    curco = 0;
    for (auto el : coolle) {
        dfsl(el);
    }
    for (auto el : coolri) {
        dfsr(el);
        curco++;
    }
    int logn = 3, vallog = 1;
    while (vallog < n) {
        vallog *= 2;
        logn++;
    }
    vector<vector<int>> upstl(logn, vector<int>(n)), upstr(logn, vector<int>(n));
    for (int i = 0; i < n; i++) {
        upstl[0][i] = par_to_lef[i];
        upstr[0][i] = par_to_rig[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]];
            upstr[j][i] = upstr[j - 1][upstr[j - 1][i]];
        }
    }
    for (int qw = 0; qw < q; qw++) {
        int s, e;
        cin >> s >> e;
        s--;
        e--;
        if (col[s] != col[e] || ini[s][0] >= ini[e][1]) {
            cout << "impossible" << '\n';
            continue;
        }
        if (s == e) {
            cout << 0 << '\n';
            continue;
        }
        int curv = s;
        for (int i = logn - 1; i >= 0; i--) {
            if (ini[upstr[i][curv]][1] < ini[e][0])
                curv = upstr[i][curv];
        }
        int curu = e;
        for (int i = logn - 1; i >= 0; i--) {
            if (ini[upstl[i][curu]][0] > ini[curv][1]) {
                curu = upstl[i][curu];
            }
        }
        int nv = curv;
        if (ini[curv][1] < ini[curu][0])
            nv = par_to_rig[curv];
        if (ini[nv][1] < ini[curu][0] || ini[nv][1] > ini[curu][1]) {
            nv = curv;
            int nu = par_to_lef[curu];
            if (ini[nv][1] < ini[nu][0] || ini[nv][1] > ini[nu][1]) {
                cout << "impossible" << '\n';
            } else {
                cout << dtr[s] - dtr[nv] + dtl[e] - dtl[nu] + 1 << '\n';
            }
        } else {
            cout << dtr[s] - dtr[nv] + dtl[e] - dtl[curu] + 1 << '\n';
        }
    }
}

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