#include <stdlib.h> #include <string.h> #include "bits/stdc++.h" #include "floppy.h" namespace { constexpr int inf = int(1E9) + 5; }; void read_array(int subtask_id, const std::vector<int> &v) { // std::string bits = "001100"; // save_to_floppy(bits); int N = int(v.size()); std::string s; std::vector<int> stk; for (int i = 0; i < N; ++i) { while (!stk.empty() && v[stk.back()] < v[i]) { s += '0'; stk.pop_back(); } s += '1'; stk.emplace_back(i); } save_to_floppy(s); } std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) { // std::vector<int> answers = {0, 0, 0, 0, 1, 2, 2, 2, 2, 3}; // return answers; int Q = int(a.size()); std::vector<int> ans(Q); std::vector<std::vector<int>> ask(N); for (int i = 0; i < Q; ++i) { ask[b[i]].emplace_back(i); } std::vector<int> stk; std::vector<int> prv(N); int p = 0; for (int i = 0; i < N; ++i) { while (bits[p] != '1') { p++; stk.pop_back(); } prv[i] = stk.empty() ? -1 : stk.back(); stk.emplace_back(i); p++; for (auto q : ask[i]) { int x = i; while (prv[x] >= a[q]) { x = prv[x]; } ans[q] = x; } } return ans; }