#include <bits/stdc++.h> #include "floppy.h" using namespace std; void read_array(int subtask_id, const vector<int> &v) { map<int, int> mp; vector<int> flt = v; sort(flt.begin(), flt.end()); flt.erase(unique(flt.begin(), flt.end()), flt.end()); for(int i = 0; i < flt.size(); i ++) mp[flt[i]] = i; string ans; int n = v.size(); int lg = 31 - __builtin_clz(n - 1); for(int i = 0; i < n; i ++) { int cur = mp[v[i]]; for(int j = lg; j >= 0; j --) { if(cur & (1 << j)) ans.push_back('1'); else ans.push_back('0'); } } save_to_floppy(ans); } struct segtr { int n; vector<int> tr; vector<int> a; segtr(int n, vector<int> const& a):n(n), tr(n << 1, -1), a(a) { for(int i = n; i < (n << 1); ++ i) tr[i] = i - n; for(int i = n - 1; i > 0; -- i) { if(a[tr[i << 1]] > a[tr[i << 1 | 1]]) tr[i] = tr[i << 1]; else tr[i] = tr[i << 1 | 1]; } } int query(int l, int r) { int ret = l; for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1) { if(l & 1) { if(a[ret] < a[tr[l]]) ret = tr[l]; l++; } if(r & 1) { --r; if(a[ret] < a[tr[r]]) ret = tr[r]; } } return ret; } }; vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) { vector<int> ans; vector<int> vals; int bs = bits.size() / N; for(int i = 0; i < bits.size(); i += bs) { int crr = 0; for(int j = 0; j < bs; j ++) { crr <<= 1; if(bits[i + j] == '1') crr |= 1; } vals.push_back(crr); } segtr tr(N, vals); for(int i = 0; i < a.size(); i ++) { ans.push_back(tr.query(a[i], b[i])); } return ans; }