#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); const int LG = std::__lg(N); std::vector<int> stk; std::vector<std::vector<int>> prv(LG + 1, std::vector<int>(N)); int p = 0; for (int i = 0; i < N; ++i) { while (bits[p] != '1') { p++; stk.pop_back(); } prv[0][i] = stk.empty() ? -1 : stk.back(); stk.emplace_back(i); p++; } for (int i = 1; i <= LG; ++i) { for (int j = 0; j < N; ++j) { if (prv[i - 1][j] == -1) { prv[i][j] = -1; } else { prv[i][j] = prv[i - 1][prv[i - 1][j]]; } } } for (int i = 0; i < Q; ++i) { int x = b[i]; for (int j = LG; j >= 0; --j) { if (prv[j][x] >= a[i]) { x = prv[j][x]; } } ans[i] = x; } return ans; }