제출 #1257705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257705		antonn	장애물 (IOI25_obstacles)	C++20	37 / 100	2097 ms	136892 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;

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;
    }
    
    auto get = [&](int l, int c) -> pair<int, int> {
        int low = 0, high = c, sol1 = c;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (H[zh.get_max(mid, c)] < T[l]) {
                sol1 = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        low = c;
        high = m - 1;
        int sol2 = c;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (H[zh.get_max(c, mid)] < T[l]) {
                sol2 = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return {sol1, sol2};
    };
    
    mx.assign(m, {-1, -1});
    for (auto [l, r] : segs) {
        pair<int, int> inter = {l, r};
        while (true) {
            int l = inter.first;
            int r = inter.second;
            int p = zh.get_min(l, r);
            int best = zt.get_max(0, far[p]);
            inter = get(best, p);
            if (inter == make_pair(l, r)) break;
        }
        for (int i = l; i <= r; i++) {
            mx[i] = inter;
        }
    }
}

bool can_reach(int l, int r, int s, int d) {
    return mx[s] == mx[d];
}

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