제출 #1320118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320118		lucas110550	장애물 (IOI25_obstacles)	C++20	83 / 100	140 ms	39440 KiB

obstacles

#include <vector>
#include <algorithm>
#include <set>
#include <cmath>

using namespace std;

vector<int> T, H;
int N, M;
vector<int> pref_min, pref_max;
vector<int> depth;
vector<vector<int>> st;
vector<int> log2_;
vector<int> parent;
vector<int> sz;

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    parent[b] = a;
    sz[a] += sz[b];
}

void init_sparse() {
    log2_.resize(M + 1);
    for (int i = 2; i <= M; ++i) log2_[i] = log2_[i / 2] + 1;
    int K = log2_[M] + 1;
    st.assign(K, vector<int>(M));
    for (int i = 0; i < M; ++i) st[0][i] = H[i];
    for (int k = 1; k < K; ++k) {
        int len = 1 << k;
        for (int i = 0; i + len <= M; ++i) {
            st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        }
    }
}

int get_max(int l, int r) {
    int k = log2_[r - l + 1];
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

void initialize(vector<int> _T, vector<int> _H) {
    T = _T;
    H = _H;
    N = T.size();
    M = H.size();

    // prefix min and max of T
    pref_min.resize(N);
    pref_max.resize(N);
    pref_min[0] = pref_max[0] = T[0];
    for (int i = 1; i < N; ++i) {
        pref_min[i] = min(pref_min[i - 1], T[i]);
        pref_max[i] = max(pref_max[i - 1], T[i]);
    }

    // depth[j] = first row where prefix_min <= H[j] (or N)
    depth.assign(M, N);
    vector<pair<int, int>> cols(M);
    for (int j = 0; j < M; ++j) cols[j] = {H[j], j};
    sort(cols.begin(), cols.end(), greater<pair<int, int>>()); // descending by H
    int ptr = 0;
    for (int i = 0; i < N; ++i) {
        int cur_min = pref_min[i];
        while (ptr < M && cols[ptr].first >= cur_min) {
            depth[cols[ptr].second] = i;
            ++ptr;
        }
    }

    // range maximum queries on H
    init_sparse();

    // DSU initialization
    parent.resize(M);
    sz.assign(M, 1);
    for (int i = 0; i < M; ++i) parent[i] = i;

    // process only columns that are free on row 0 (depth > 0)
    vector<pair<int, int>> good; // (key, index)
    for (int j = 0; j < M; ++j) {
        if (depth[j] > 0) {
            int L = depth[j] - 1;
            int key = pref_max[L];
            good.emplace_back(key, j);
        }
    }

    // sort by key descending
    sort(good.begin(), good.end(), greater<pair<int, int>>());

    set<int> active; // set of indices already processed (good columns)
    for (auto& p : good) {
        int key = p.first;
        int idx = p.second;
        auto it = active.lower_bound(idx);

        // try to connect with the nearest column on the left
        if (it != active.begin()) {
            int left = *prev(it);
            int mx = get_max(left, idx);
            if (mx < key) unite(idx, left);
        }

        // try to connect with the nearest column on the right
        if (it != active.end()) {
            int right = *it;
            int mx = get_max(idx, right);
            if (mx < key) unite(idx, right);
        }

        active.insert(idx);
    }
}

bool can_reach(int L, int R, int S, int D) {
    // constraints guarantee L = 0, R = M-1, so the whole grid is available.
    return find(S) == find(D);
}

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