제출 #1307750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307750		fafnir	장애물 (IOI25_obstacles)	C++20	24 / 100	499 ms	43220 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
int lf[MAXN];
// rt[i] := First column right of column i having smaller humidity
int rt[MAXN];


int pl[19][MAXN];
int pr[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(rt[i], 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]; }
    }


    // 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];
            pl[i][j] = pl[i-1][left];

            int right = pr[i-1][j];
            pr[i][j] = pr[i-1][right];

        }
    }

}

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--){
        s = pr[i][s];
    }
    for(int i=18;i>=0;i--){
        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: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17