#include "floppy.h" #include <bits/stdc++.h> using namespace std; void read_array(int subtask_id, const vector<int> &v) { string res = ""; vector<int> vec; int n = v.size(); for(int i = 0; i < n; i++){ while(!vec.empty() && v[vec.back()] < v[i]){ vec.pop_back(); res += "0"; } vec.push_back(i); res += "1"; } save_to_floppy(res); } const int mxn = 1e5, lg2 = 17; int child[mxn][2]; int suc[mxn][lg2]; int tin[mxn],tout[mxn],tim=0; void dfs(int u){ tin[u] = tim++; for(int i = 1; i < lg2; i++) suc[u][i] = suc[suc[u][i-1]][i-1]; int v = child[u][0]; if(v!=-1){ suc[v][0] = u; dfs(v); } v = child[u][1]; if(v!=-1){ suc[v][0] = u; dfs(v); } tout[u] = tim++; } bool is_anc(int u, int v){ return tin[u]<=tin[v] && tout[v]<=tout[u]; } int get_lca(int u, int v){ if(is_anc(u,v)) return u; if(is_anc(v,u)) return v; for(int i = lg2-1; i >= 0; i--) if(!is_anc(suc[u][i],v)) u = suc[u][i]; return suc[u][0]; } vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) { for(int i = 0; i < N; i++) child[i][0] = child[i][1] = -1; vector<int> vec; for(int i = 0, j = 0; i < N; i++){ while(bits[j]=='0'){ child[i][0] = vec.back(); vec.pop_back(); j++; } if(!vec.empty()) child[vec.back()][1] = i; j++; vec.push_back(i); } dfs(vec[0]); int q = a.size(); vector<int> res(q); for(int i = 0; i < q; i++) res[i] = get_lca(a[i],b[i]); return res; // vector<int> answers = {0, 0, 0, 0, 1, 2, 2, 2, 2, 3}; // return answers; }