제출 #1319957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319957		Rainmaker2627	장애물 (IOI25_obstacles)	C++20	0 / 100	67 ms	38820 KiB

obstacles

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

struct segtree {
    int n;
    vector<int> st;

    void init(vector<int>& v) {
        n=v.size();
        st.assign(2*n, 0);
        for (int i = n; i < 2*n; ++i) st[i]=v[i-n];
        for (int i = n-1; i > 0; --i) st[i]=max(st[2*i], st[2*i+1]);
    }

    int query(int a, int b) {
        int s=-1;
        a+=n; b+=n;
        while (a<=b) {
            if (a%2==1) s=max(s, st[a++]);
            if (b%2==0) s=max(s, st[b--]);
            a/=2; b/=2;
        } return s;
    }
};

int N, M, lg;
segtree st;
vector<int> premin, premax, downtemp;
vector<vector<int>> plbj, prbj, boundl, boundr; // prefer left/right: not binding

//                               N                   M
void initialize(std::vector<int> T, std::vector<int> H) {
    // max segtree for humidity
    st.init(H);

    // prefix max/min for temp
    N=T.size();
    premin.assign(N, T[0]);
    premax.assign(N, T[0]);
    for (int i = 1, j = 0; i < N; i++) {
        premin[i]=min(premin[i-1], T[i]);
        premax[i]=max(premax[i-1], T[i]);
    }
    
    // minimum temp you can get by going only down: for blift later
    M=H.size();
    downtemp.assign(M, 0);
    for (int i = 0; i < M; i++) {
        int l=0, r=N-1;
        while (l<r) {
            int mid=(l+r)/2;
            if (premin[mid]<=H[i]) r=mid;
            else l=mid+1;
        } downtemp[i]=premax[r];
    }
    
    // we need to find the 0 case for the blifting -- monotone stack
    lg=0;
    while (M>(1<<lg)) lg++;
    plbj.assign(lg+1, vector<int>(M, -1));
    prbj.assign(lg+1, vector<int>(M, -1));
    stack<int> s;
    for (int i = 0; i < M; i++) {
        while (!s.empty() && H[s.top()]>H[i]) {
            prbj[0][s.top()]=i; s.pop();
        } if (!s.empty()) {
            if (H[s.top()]==H[i]) plbj[0][i]=plbj[0][s.top()];
            else plbj[0][i]=s.top();
        } s.push(i);
    }

    // after monotone stack check if we can actually reach that point, -1 means we cant
    // bl=how far are we forced to go left if we are trying to jump right?
    plbj.assign(lg+1, vector<int>(M));
    prbj.assign(lg+1, vector<int>(M));
    for (int i = 0; i < M; i++) {
        if (plbj[0][i]==-1 || st.query(plbj[0][i], i)>=downtemp[i]) plbj[0][i]=i;
        if (prbj[0][i]==-1 || st.query(i, prbj[0][i])>=downtemp[i]) prbj[0][i]=i;

        boundl[0][i]=boundr[0][i]=i;
        if (plbj[0][i]==i && prbj[0][i]>i) plbj[0][i]=prbj[0][i], boundr[0][i]=prbj[0][i];
        if (prbj[0][i]==i && plbj[0][i]<i) prbj[0][i]=plbj[0][i], boundl[0][i]=plbj[0][i];
    }

    // propogate bjumping and manage boundary
    for (int i = 1; i <= lg; i++) {
        for (int j = 0; j < M; j++) {
            prbj[i][j]=prbj[i-1][prbj[i-1][j]];
            plbj[i][j]=plbj[i-1][plbj[i-1][j]];
            boundl[i][j]=min(boundl[i-1][j], boundl[i-1][prbj[i-1][j]]);
            boundr[i][j]=max(boundr[i-1][j], boundr[i-1][plbj[i-1][j]]);
        }
    }

    return;
}

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

    // blift S right and D left until reachable or until out of bounds
    // impl without L,R first because im just checking if this works
    for (int i = lg; i >= 0; i--) {
        if (boundl[i][s]<L) continue;
        s=prbj[i][s];
    }

    for (int i = lg; i >= 0; i--) {
        if (boundr[i][s]>R) continue;
        d=plbj[i][d];
    }

    // cerr << "starting from S we can reach " << s << '\n';
    // cerr << "starting from D we can reach " << d<< '\n';
    // cerr << "which have maxtemp as follows " << downtemp[s] << ' ' << downtemp[d] << '\n';

    return st.query(min(s, D), max(s, D))<downtemp[s] && st.query(min(d, S), max(d, S))<downtemp[d];
}

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