#include "obstacles.h" #include<bits/stdc++.h> using namespace std; int n,m,lenA,lenB,lenT; vector<int>a,b,ter,c; bool subtask3=0; bool check(vector<int>&v,int&start,int&end){ auto ub=upper_bound(v.begin(),v.end(),start); return ub==v.end()||*ub>end; } void initialize(vector<int>T,vector<int>H){ n=(int)T.size(),m=(int)H.size(); if(T==vector<int>{2,1,3})subtask3=1; for(int i=0;i<m;i++){ if(H[i]>=3)ter.push_back(i); if(H[i]>=T[0])a.push_back(i); if(H[i]>=T[n-1])c.push_back(i); if(!H[i])b.push_back(i); } lenA=(int)a.size(),lenB=(int)b.size(),lenT=(int)ter.size(); return; } bool can_reach(int l,int r,int s,int d){ if(s>d)swap(s,d); if(n==1)return check(a,s,d); if(subtask3){ int idx=upper_bound(ter.begin(),ter.end(),s)-ter.begin(); if(idx!=lenT&&ter[idx]<d)return 0; int i1=upper_bound(a.begin(),a.end(),s)-a.begin(); if(i1==lenA||a[i1]>d)return 1; int i2=lower_bound(b.begin(),b.end(),s)-b.begin(); if(i2!=lenB&&b[i2]<a[i1]||i2-1>=0&&(i1-1<0||b[i2-1]>a[i1-1])){} else return 0; int ub=upper_bound(a.begin(),a.end(),d)-a.begin(); int lb=lower_bound(b.begin(),b.end(),d)-b.begin(); if(lb-1>=0&&(ub-1<0||b[lb-1]>a[ub-1]))return 1; if(lb!=lenB&&(ub==lenA||b[lb]<a[ub]))return 1; return 0; } return check(c,s,d); }