#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
const int Nn = 2e5 + 5;
string s;
int n, tr, root, a[Nn], T[Nn], L[Nn], R[Nn];
int depth, dep[Nn], P[Nn][22], idx[Nn];
int Lc[Nn], Rc[Nn];
inline void dfs(int x) {
if (Lc[x] != -1)
s += '1', dfs(Lc[x]);
else
s += '0';
if (Rc[x] != -1)
s += '1', dfs(Rc[x]);
else
s += '0';
}
void read_array(int subtask_id, const vector<int> &v) {
n = v.size();
for (int i = 0; i < n; ++i) {
Lc[i + 1] = Rc[i + 1] = -1;
a[i + 1] = v[i];
}
a[0] = 1e9 + 1;
deque < int > dql;
dql.push_back(0);
for (int i = 1; i <= n; ++i) {
while (a[dql.back()] < a[i])
dql.pop_back();
L[i] = dql.back();
dql.push_back(i);
}
a[n + 1] = 1e9 + 1;
deque < int > dqr;
dqr.push_back(n + 1);
for (int i = n; i >= 1; --i) {
while (a[dqr.back()] < a[i])
dqr.pop_back();
R[i] = dqr.back();
dqr.push_back(i);
}
for (int i = 1; i <= n; ++i) {
if (L[i] == 0 && R[i] == n + 1) {
root = i;
}
}
for (int i = 1; i <= n; ++i) {
if (L[i] != 0) {
if (Rc[L[i]] == -1 || a[Rc[L[i]]] < a[i]) {
Rc[L[i]] = i;
}
}
if (R[i] != n + 1) {
if (Lc[R[i]] == -1 || a[Lc[R[i]]] < a[i]) {
Lc[R[i]] = i;
}
}
}
dfs(root);
save_to_floppy(s);
return ;
}
inline int LCA(int a, int b) {
if (a == b) return a;
if (dep[a] < dep[b]) swap(a, b);
for (int i = 19; i >= 0; --i)
if (dep[P[a][i]] >= dep[b]) a = P[a][i];
if (a == b) return a;
for (int i = 19; i >= 0; --i)
if (P[a][i] != P[b][i]) a = P[a][i], b = P[b][i];
return P[a][0];
}
inline void ufs(int x, int l, int r) {
idx[x] = r - (Rc[x] - Lc[x]);
dep[idx[x]] = ++depth;
if (L[x]) {
ufs(L[x], l, r - (Rc[x] - Lc[x] + 1));
P[idx[L[x]]][0] = idx[x];
}
if (R[x]) {
ufs(R[x], l + (Lc[x] - x + 1), r);
P[idx[R[x]]][0] = idx[x];
}
--depth;
}
vector < int > solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
n = N;
tr = 1;
s = bits;
int q = a.size();
deque < int > dq;
dq.push_back(tr);
for (int i = 1; i <= n; ++i) {
Lc[i] = Rc[i] = 0;
L[i] = R[i] = 0;
}
for (int i = 0; i < s.size(); ++i) {
if (!T[dq.back()]) {
T[dq.back()] = 1;
if (s[i] == '1') {
L[dq.back()] = ++tr;
dq.push_back(tr);
}
else {
Lc[dq.back()] = tr;
}
}
else
if (T[dq.back()]) {
T[dq.back()] = 2;
if (s[i] == '1') {
R[dq.back()] = ++tr;
dq.push_back(tr);
}
else {
while (dq.size() && T[dq.back()] == 2) {
Rc[dq.back()] = tr;
dq.pop_back();
}
if (dq.size() && T[dq.back()] == 1) {
Lc[dq.back()] = tr;
}
}
}
}
ufs(1, 0, n);
P[idx[1]][0] = idx[1];
for (int j = 1; j < 20; ++j)
for (int i = 1; i <= n; ++i)
P[i][j] = P[P[i][j - 1]][j - 1];
vector < int > answers;
for (int i = 0; i < q; ++i) {
answers.push_back(LCA(a[i] + 1, b[i] + 1) - 1);
}
return answers;
}
Compilation message
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int i = 0; i < s.size(); ++i) {
| ~~^~~~~~~~~~
stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
101 | if (query_answers.size() != M) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
768 KB |
Output is correct |
| 2 |
Correct |
2 ms |
776 KB |
Output is correct |
| 3 |
Correct |
2 ms |
804 KB |
Output is correct |
| 4 |
Correct |
2 ms |
792 KB |
Output is correct |
| 5 |
Correct |
3 ms |
792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
4512 KB |
Output is correct |
| 2 |
Correct |
30 ms |
4536 KB |
Output is correct |
| 3 |
Correct |
28 ms |
4936 KB |
Output is correct |
| 4 |
Correct |
28 ms |
4772 KB |
Output is correct |
| 5 |
Correct |
30 ms |
4592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
16972 KB |
Output is correct |
| 2 |
Correct |
139 ms |
16948 KB |
Output is correct |
| 3 |
Correct |
129 ms |
18000 KB |
Output is correct |
| 4 |
Correct |
111 ms |
17912 KB |
Output is correct |
| 5 |
Correct |
112 ms |
17048 KB |
Output is correct |
