#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> temp;
vector<int> hum;
int rows;
int cols;
vector<set<int>> bad;
set<int> good;
void initialize(std::vector<int> T, std::vector<int> H) {
temp = T;
hum = H;
rows = T.size();
cols = H.size();
bad.resize(T.size());
for(int i = 0; i < H.size(); i ++){
for(int j = 0; j < T.size(); j ++){
if(H[i] >= T[j]){
bad[j].insert(i);
}
}
if(H[i] < T[1]) good.insert(i);
}
}
struct Coord {
int i;
int j;
vector<Coord> get_adj(){
vector<Coord> res;
if(i > 0) res.push_back({i-1, j});
if(j > 0) res.push_back({i, j-1});
if(i < rows - 1) res.push_back({i+1, j});
if(j < cols - 1) res.push_back({i, j+1});
return res;
}
bool operator==(const Coord& other) const {
return (i==other.i) && (j==other.j);
}
};
struct Hash {
size_t operator()(const Coord& c) const {
size_t h1 = hash<int>{}(c.i);
size_t h2 = hash<int>{}(c.j);
return h1 ^ (h2 << 1);
}
};
// Return index of closest obstacle
int look_left(int x, set<int>& se){
auto it = se.lower_bound(x);
if(it == se.begin()) return -1;
it --;
return *it;
}
int look_right(int x, set<int>& se){
auto it = se.lower_bound(x);
if(it == se.end()) return INT_MAX / 2;
return *it;
}
bool can_reach(int L, int R, int S, int D) {
if(S > D) swap(S, D);
// Check if we can go through the top row
int block_right = look_right(S, bad[0]);
int block_left = look_left(D, bad[0]);
if(block_right > D) return true;
// Have to go down
int open_left = look_left(block_right, good);
if(open_left == -1) return false;
int right = look_right(open_left, bad[2]);
int open_right = look_right(block_left + 1, good);
if(open_right > R) return false;
int left = look_left(open_right, bad[2]);
if(left < right) return true;
return false;
}
/*
g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o obstacles grader2.cpp obstacles.cpp
1 5
5
1 1 1 6 1
2
0 3 0 4
0 3 0 2
3 4
2 1 3
0 1 2 0
1
0 3 1 3
*/
