# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1253542 | nickolasarapidis | Obstacles for a Llama (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int N, M;
vector<int> T(MAXN), H(MAXN), ST(4*MAXN);
void build(int v, int l, int r){
if(l == r){
ST[v] = H[l];
return;
}
int m = (l + r)/2;
build(2*v, l, m);
build(2*v + 1, m + 1, r);
ST[v] = max(ST[2*v], ST[2*v + 1]);
return;
}
int query(int v, int l, int r, int a, int b){
if(l > b or r < a) return -1;
if(l >= a and r <= b) return ST[v];
int m = (l + r)/2;
return max(query(2*v, l, m, a, b), query(2*v + 1, m + 1, r, a, b));
}
bool can_reach(l, r, s, d){
if(query(1, 0, M - 1, s, d) >= T[N - 1]) return false;
else return true;
}
void initialize(vector<int> A, vector<int> B){
N = A.size(); M = B.size();
T = A; H = B;
build(1, 0, M - 1);
}