#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5+1; const vector<pair<int,int>>moves = {{-1,0},{0,1},{1,0}};// add 0,-1 int n,m; const int MAXLOG = 18; map<int,bool>vis; vector<vector<tuple<int,int,int>>>p; vector<int>t,h; int dist[MAXN]; bool marked[MAXN]; void dfs(int u,int v,int last_l,int last_r,int last_p){ if(vis.find(u*m+v)!=vis.end()){ //cout << last_l << " " << last_r << " -- " << u << " " << v << endl; return; }vis[u*m+v]=true; if(u==0)marked[v]=true; if(t[u]<=h[v])return; if(u==0){ p[0][v] = {last_l,last_r,last_p}; if(v==last_p)dist[v]=0; else dist[v]=dist[last_p]+1; //cout << v << " - " << last_p << "--" << last_l << "A" << last_r << endl; last_p = v; last_l=last_r=v; } for(auto it : moves){ if(it.first+u<n&&it.first+u>=0&&it.second+v<m&&it.second+v>=0&&(vis.find((it.first+u)*m+(it.second+v))==vis.end())){ dfs(it.first+u,it.second+v,min(last_l,v+it.second),max(last_r,v+it.second),last_p); } }return; } // tips to make it work: /* -make dfs quicker, just 100ms, or change map with coords (or use arrays) */ void initialize(std::vector<int> T, std::vector<int> H){ t = T,h=H; n = T.size(); m=H.size(); //dist.resize(m+2,-1); //marked.resize(m+2,0); p.resize(MAXLOG,vector<tuple<int,int,int>>(m+2,{-1,-1,-1})); //vis.resize(n+2,vector<bool>(m+2,0)); for(int i=0;i<m;i++){ if(!marked[i]){ dfs(0,i,i,i,i); vis.clear(); } } for(int k=1;k<MAXLOG;k++){ //cout << "XX" << k<< endl; for(int i=m-1;i>=0;i--){ //cout << i << "::" <<get<2>(p[k-1][i]) << endl; if(get<2>(p[k-1][i])!=-1){ p[k][i]=p[k-1][get<2>(p[k-1][i])]; get<0>(p[k][i])=min(get<0>(p[k][i]),get<0>(p[k-1][i])); get<1>(p[k][i])=max(get<1>(p[k][i]),get<1>(p[k-1][i])); } } } } int get_lca(int a,int b){ for(int i=MAXLOG-1;i>=0;i--){ if(get<2>(p[i][a])!=get<2>(p[i][b])){ a = get<2>(p[i][a]); b = get<2>(p[i][b]); } }int lca = get<2>(p[0][a]); if(get<2>(p[0][a])!=get<2>(p[0][b]))return -1; return lca; } void get_kth(int &A,int cant){ for(int i=MAXLOG-1;i>=0;i--){ if(cant&(1LL<<i))A = get<2>(p[i][A]); } return; } tuple<int,int,int> get_until(int a,int& b){ tuple<int,int,int>cur = {1e9,-1e9,0}; for(int i = MAXLOG-1;i>=0;i--){ if(get<2>(p[i][a])<b){ get<0>(cur)=min(get<0>(cur),get<0>(p[i][a])); get<1>(cur)=max(get<1>(cur),get<1>(p[i][a])); a = get<2>(p[i][a]); } }if(a<b&&get<2>(p[0][a])==b){ get<0>(cur)=min(get<0>(cur),get<0>(p[0][a])); get<1>(cur)=max(get<1>(cur),get<1>(p[0][a])); a = get<2>(p[0][a]); } return cur; } bool can_reach(int L, int R, int S, int D){ if(S<L||R<D||dist[S]==-1||dist[D]==-1)return false; // then kth if(dist[S]>dist[D])swap(S,D); if(dist[S]!=dist[D])get_kth(D,dist[D]-dist[S]); // get LCA, then get dist int lca = get_lca(S,D); if(lca==-1)return false; tuple<int,int,int>L1 = get_until(lca,S); tuple<int,int,int>L2 = get_until(lca,D); int left = min(get<0>(L1),get<0>(L2)); int right = max(get<1>(L1),get<1>(L2)); if(L<=left&&right<=R)return true; else return false; } /* signed main(){ // just check int n,m; cin >> n >> m; vector<int>t(n),h(m); for(int i=0;i<n;i++)cin >> t[i]; for(int i=0;i<m;i++)cin >> h[i]; initialize(t,h); cout << "XX"<< endl; int q; cin >> q; while(q--){ int l,r,s,d; cin >> l >> r >> s >> d; if(can_reach(l,r,s,d))cout << "YES\n"; else cout << "NO\n"; } }*/