#include <stdlib.h> #include <string.h> #include "floppy.h" #include <bits/stdc++.h> using namespace std; #define sz(x) (int)x.size() #define all(x) x.begin() , x.end() void read_array(int subtask_id, const vector<int> &arr) { string bits; stack<int>st; for(int i = 0;i<sz(arr);i++){ while(!st.empty() and st.top() < arr[i]){ st.pop(); bits += '0'; } st.push(arr[i]); bits += '1'; } save_to_floppy(bits); } struct SEGT{ vector < pair<int,int> > t;// value index int tree_size; const pair<int,int> identity_element = {0,0}; pair<int,int> merge(pair<int,int> x , pair<int,int> y){ return max(x,y); } void init(int x){ tree_size = x+3; t.assign(2*tree_size , identity_element); } void modify(int p, pair<int,int> value) { // set value at position p for (t[p += tree_size] = value; p > 1; p >>= 1){ t[p>>1] = merge(t[p] , t[p^1]); } } int query(int l, int r) { // sum on interval [l, r] pair<int,int> res = identity_element; for (r+=1 , l += tree_size, r += tree_size; l < r; l >>= 1, r >>= 1) { if (l&1) res = merge(res , t[l++]); if (r&1) res = merge(res , t[--r]); } return res.second; } }; vector<int> solve_queries(int subtask_id, int n, const string &bits,const vector<int> &a, const vector<int> &b) { vector<int>tree[n+1]; stack<int>st; int sayac = 0 , arr[n+1]; for(int i = 1;i<=n;i++){ while(bits[sayac] == '0'){ st.pop(); sayac++; } if(!st.empty()) tree[st.top()].push_back(i); else tree[0].push_back(i); st.push(i); sayac++; } sayac = 1; function<void(int)> dfs = [&](int node){ for(auto itr : tree[node]) dfs(itr); arr[node] = sayac++; }; dfs(0); SEGT segt; segt.init(n+1); for(int i = 1;i<=n;i++){ segt.modify(i , {arr[i] , i}); } vector<int>answers; for(int i = 0;i<sz(a);i++){ answers.push_back(segt.query(a[i]+1 , b[i]+1)-1); } return answers; }