| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1316383 | ezzzay | 장애물 (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
vector<int>HH,TT;
const int N=3e5+5;
int st[N];
int N;
void build(int node, int L, int R){
if(L==R){
st[node]=HH[L-1];
return;
}
int mid=(L+R)/2;
build(node*2,L,mid);
build(node*2+1,mid+1,R);
st[node]=max(st[node*2],st[node*2+1]);
}
int find(int node, int L, int R, int l, int r){
if(l>R or L>r)return 0;
if(l<=L and R<=r)return st[node];
int mid=(L+R)/2;
return max(find(node*2,L,mid,l,r),find(node*2+1,mid+1,R,l,r));
}
void initialize(std::vector<int> T, std::vector<int> H) {
TT.clear();
HH.clear();
for(auto a:T)TT.pb(a);
for(auto b:H)HH.pb(b);
N=T.size();
build(1,1,(int)HH.size());
}
bool can_reach(int L, int R, int S, int D) {
if(S>D)swap(S,D);
int h=find(1,1,N,S+1,D+1);
return TT[0]>h;
}
