제출 #1307755

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

obstacles

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

const int INF = 1'000'000'000;
const int MAXN = 200'001;
int n;  // Number of rows (temperature)
int m;  // Number of columns (humidity)

// Prefix sums
// Index i: Min/Max of temperature up to i 
// Prefix sum among rows
vector<int> tmin, tmax;

// For each column j, pw(j) contains the maximum temperature
// reachable from column j only going down (without any obstacles)
// so it's reachable from (0,j)
int pw[MAXN];
int h[MAXN];


// lf[i] := First column left of column i having smaller humidity
//          If there is no such column lf[i] = i
//          Not necessarily directly connected to column i
// rt[i] := First column right of column i having smaller humidity
int lf[MAXN];
int rt[MAXN];


// pl[jmp][i] := Column with minimum humidity reachable from column i
//                 after at most <= 2^jmp jumps
int pl[19][MAXN];
int pr[19][MAXN];


// bl[jmp][i] := Minimum column we need to jump in order to reach pl[jmp][i]
int bl[19][MAXN];
int br[19][MAXN];



// Building segment tree
// Query O(log(n)), the maximum humidity in range [l,r]
int seg[4*MAXN];

#define LEFT(u) (2*(u)+1)
#define RIGHT(u) (2*(u)+2) 

void _build(int u, int l, int r) {
    if (l == r) {
        seg[u] = h[l];
    } else {
        int m = (l + r) / 2;
        _build(LEFT(u), l, m);
        _build(RIGHT(u), m+1, r);
        seg[u] = max(seg[LEFT(u)], seg[RIGHT(u)]);
    }
}

// sl, sr: Bounds of segment of current node
// l, r: Query bounds
int _query(int u, int l, int r, int sl, int sr) {
    if (l > r) {return -INF;}
    if (l == sl && r == sr) {return seg[u];}

    int sm = (sl + sr) / 2;
    return max(
        _query(LEFT(u), l, min(r, sm), sl, sm),
        _query(RIGHT(u), max(l, sm+1), r, sm+1, sr)
    );
}

void build() {_build(0, 0, m-1);} 

int query(int l, int r) {
    return _query(0, l, r, 0, m-1);
}


void initialize(vector<int> T, vector<int> H) {
    n = T.size();
    m = H.size();

    tmin = T;
    tmax = T;

    for (int i = 0; i < m; ++i) { h[i] = H[i]; }

    for (int i = 1; i < n; ++i) {
        tmin[i] = min(T[i], tmin[i-1]);
        tmax[i] = max(T[i], tmax[i-1]);
    }


    
    // Calculate pw(j)
    // pw(j) := For column j, index of row with greatest temperature
    //          reachable from (0,j)

    // Binary search on how far we can go maximally from (0,j)
    for (int i = 0; i < m; ++i) {
        int l = 0;
        int r = n-1;

        while (l <= r) {
            int mid = (l + r) / 2;

            // Cannot reach mid --> at most mid-1
            if (tmin[mid] <= H[i]) {
                r = mid-1;
            } else {
                l = mid+1;
            }
        }

        // r contains last index reachable from (0,j)
        // In case T[0] <= H[j], r==-1
        pw[i] = r == -1 ? -1 : tmax[r];
    }


    // Build segment tree
    build();

    stack<int> stk;
    for (int i = 0; i < m; ++i) {
        lf[i] = i;
        while (!stk.empty() && h[stk.top()] >= h[i]) {stk.pop();}
        if (!stk.empty()) {lf[i] = stk.top();}
        stk.push(i);
    }

    while (!stk.empty()) {stk.pop();}

    for (int i = m-1; i >= 0; --i) {
        rt[i] = i;
        while (!stk.empty() && h[stk.top()] >= h[i]) {stk.pop();}
        if (!stk.empty()) {rt[i] = stk.top();}
        stk.push(i);
    }


    // Binary Lifting
    // Base Case: Column with smallest humidity immediatelly left/right
    for (int i = 0; i < m; ++i) {
        pl[0][i] = pr[0][i] = i;

        // Can go left if there exists a column
        bool gol = query(lf[i], i) < pw[i] && lf[i] != i;
        bool gor = query(i, rt[i]) < pw[i] && rt[i] != i;


        if (gor) { pr[0][i] = rt[i]; }
        else if (gol) { pr[0][i] = lf[i]; }

        if (gol) { pl[0][i] = lf[i]; }
        else if (gor) { pl[0][i] = rt[i]; }

        bl[0][i] = min(i, pr[0][i]);
        br[0][i] = max(i, pl[0][i]);
    }


    // Binary Lifting
    // i-1 --> i
    for (int i = 1; i <= 18; ++i) {
        for (int j = 0; j < m; ++j) {
            int left = pl[i-1][j];
            int right = pr[i-1][j];

            pl[i][j] = pl[i-1][left];
            bl[i][j] = min(bl[i-1][j],bl[i-1][right]);

            pr[i][j] = pr[i-1][right];
            br[i][j] = max(br[i-1][j], br[i-1][left]);

        }
    }

}

bool can_reach(int L, int R, int S, int D) {
    
 if(S > D)swap(S,D);
    int s = S,d = D;

    for(int i=18;i>=0;i--){
        if (bl[i][s] >= L) {
            s = pr[i][s];
        }
    }
    for(int i=18;i>=0;i--){
        if (br[i][d] <= R) {
            d = pl[i][d];
        }
    }

    return query(min(s,D),max(s,D)) < pw[s] 
        && query(min(S,d),max(S,d)) < pw[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: 17 / 17