제출 #1257998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257998		antonn	장애물 (IOI25_obstacles)	C++20	31 / 100	165 ms	140988 KiB

obstacles

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) a.begin(), a.end()

struct SparseTable {
    int n;
    vector<int> lg;
    vector<vector<pair<int, int>>> mn;
    vector<vector<pair<int, int>>> mx;
    
    SparseTable(vector<int> a) {
        n = a.size();
        lg.assign(n + 1, 0);
        mn.assign(20, vector<pair<int, int>>(n + 1));
        mx.assign(20, vector<pair<int, int>>(n + 1));
        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i / 2] + 1;
        }
        for (int i = 0; i < n; i++) {
            mn[0][i] = mx[0][i] = {a[i], i};
        }
        for (int h = 1; h < 20; h++) {
            for (int i = 0; i + (1 << h) - 1 < n; i++) {
                mn[h][i] = min(mn[h - 1][i], mn[h - 1][i + (1 << (h - 1))]);
                mx[h][i] = max(mx[h - 1][i], mx[h - 1][i + (1 << (h - 1))]);
            }
        }
    }
    
    int get_min(int l, int r) {
        assert(l <= r);
        int p = lg[r - l + 1];
        return min(mn[p][l], mn[p][r - (1 << p) + 1]).second;
    }
    
    int get_max(int l, int r) {
        assert(l <= r);
        int p = lg[r - l + 1];
        return max(mx[p][l], mx[p][r - (1 << p) + 1]).second;
    }
};

vector<pair<int, int>> mx;
vector<int> t, sz;

int root(int x) {
    if (t[x] == x) return x;
    return t[x] = root(t[x]);
}

void join(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    t[b] = a;
    sz[a] += sz[b];
}

void initialize(vector<int> T, vector<int> H) {
    int n = T.size();
    int m = H.size();
    vector<pair<int, int>> segs;
    int l = -1, r = -1;
    for (int i = 0; i < m; i++) {
        if (T[0] > H[i]) {
            if (l == -1) {
                l = i;
            }
            r = i;
        } else {
            if (l != -1) {
                segs.push_back({l, r});
            }
            l = r = -1;
        }
    }
    if (l != -1) segs.push_back({l, r});
    SparseTable zt(T), zh(H);
    
    vector<int> far(m);
    for (int i = 0; i < m; i++) {
        int low = 0, high = n - 1, sol = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (H[i] < T[zt.get_min(0, mid)]) {
                sol = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        far[i] = sol;
    }
    t.resize(m);
    sz.resize(m);
    for (int i = 0; i < m; i++) {
        t[i] = i;
        sz[i] = 1;
    }
    
    vector<int> lft(m, -1), rgh(m, m);
    vector<int> stk;
    for (int i = 0; i < m; i++) {
        while (!stk.empty() && H[i] <= H[stk.back()]) stk.pop_back();
        if (!stk.empty()) lft[i] = stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for (int i = m - 1; i >= 0; i--) {
        while (!stk.empty() && H[i] <= H[stk.back()]) stk.pop_back();
        if (!stk.empty()) rgh[i] = stk.back();
        stk.push_back(i);
    }
    
    mx.assign(m, {-1, -1});
    for (auto [l, r] : segs) {
        for (int i = l; i <= r; i++) {
            if (i + 1 <= r) join(i, i + 1);
            int best = zt.get_max(0, far[i]);
            if (lft[i] != -1 && T[best] > H[zh.get_max(lft[i], i)]) {
                join(i, lft[i]);
                //cout << "CAN REACH " << i << " " << lft[i] << "\n";
            }
            if (rgh[i] != m && T[best] > H[zh.get_max(i, rgh[i])]) {
                //cout << "CAN REACH " << i << " " << rgh[i] << "\n";
                join(i, rgh[i]);
            }
        }
    }
}

bool can_reach(int l, int r, int s, int d) {
    return root(s) == root(d);
}

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