제출 #1307390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307390		fafnir	장애물 (IOI25_obstacles)	C++20	0 / 100	2095 ms	7356 KiB

obstacles

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

static const int LOG = 20;

int N, M;
vector<int> T, H;
vector<int> L, R;
vector<int> parent;
int up[LOG][200005];

/* --- Step 1: Initialize --- */
void initialize(vector<int> _T, vector<int> _H) {
    T = _T;
    H = _H;
    N = T.size();
    M = H.size();

    vector<int> ord(M);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return H[a] < H[b];
    });

    L.assign(N, M);
    R.assign(N, -1);

    /* Each row interval */
    for (int i = 0; i < N; i++) {
        int pos = lower_bound(
            ord.begin(),
            ord.end(),
            T[i],
            [&](int idx, int val) {
                return H[idx] < val;
            }
        ) - ord.begin();

        if (pos == 0) continue;
        for (int j = 0; j < pos; j++) {
            L[i] = min(L[i], ord[j]);
            R[i] = max(R[i], ord[j]);
        }
    }

    /* --- Step 2: Build containment tree --- */
    parent.assign(N, -1);
    vector<int> stk;

    vector<int> rows(N);
    iota(rows.begin(), rows.end(), 0);

    sort(rows.begin(), rows.end(), [&](int a, int b) {
        if (L[a] != L[b]) return L[a] < L[b];
        return R[a] > R[b];
    });

    for (int i : rows) {
        while (!stk.empty() &&
               !(L[stk.back()] <= L[i] && R[i] <= R[stk.back()])) {
            stk.pop_back();
        }
        parent[i] = stk.empty() ? -1 : stk.back();
        stk.push_back(i);
    }

    /* --- Step 3: Binary lifting --- */
    for (int i = 0; i < N; i++)
        up[0][i] = parent[i];

    for (int k = 1; k < LOG; k++) {
        for (int i = 0; i < N; i++) {
            int p = up[k - 1][i];
            up[k][i] = (p == -1 ? -1 : up[k - 1][p]);
        }
    }
}

/* climb up while interval stays inside [ql, qr] */
int climb(int v, int ql, int qr) {
    for (int k = LOG - 1; k >= 0; k--) {
        int p = up[k][v];
        if (p != -1 &&
            L[p] >= ql &&
            R[p] <= qr) {
            v = p;
        }
    }
    return v;
}

/* --- Step 4: Queries --- */
bool can_reach(int ql, int qr, int S, int D) {
    int a = -1, b = -1;

    for (int i = 0; i < N; i++) {
        if (L[i] <= S && S <= R[i] &&
            L[i] >= ql && R[i] <= qr) {
            a = i; break;
        }
    }

    for (int i = 0; i < N; i++) {
        if (L[i] <= D && D <= R[i] &&
            L[i] >= ql && R[i] <= qr) {
            b = i; break;
        }
    }

    if (a == -1 || b == -1) return false;

    a = climb(a, ql, qr);
    b = climb(b, ql, qr);

    if (a == b) return true;

    /* check intersection */
    return max(L[a], L[b]) <= min(R[a], R[b]);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17