#include <bits/stdc++.h>
#include "floppy.h"
#define INF 1000000005
#define EPS 1e-6
#define pb push_back
#define pause system("pause")
#define exit exit(0)
#define endl '\n'
using namespace std;
using ull = unsigned long long;
using ll = long long;
typedef pair<int, int> pii;
const int N = 40005, LG = 16;
int n, m;
int st[LG][N], lg[N], ar[N];
string tr_ans;
int get(int l, int r) {
int j = lg[r - l + 1];
int f = st[j][l], s = st[j][r - (1 << j) + 1];
return ar[f] > ar[s] ? f : s;
}
void dfs(int l, int r) {
if (l > r) return;
int j = get(l, r);
tr_ans += '0' + (l <= j - 1);
tr_ans += '0' + (j + 1 <= r);
dfs(l, j - 1);
dfs(j + 1, r);
}
void read_array(int subtask_id, const vector<int> &v) {
vector<int> a(v.begin(), v.end());
sort(a.begin(), a.end());
int n = v.size(), i = 0;
for (auto x : v) {
int j = lower_bound(a.begin(), a.end(), x) - a.begin();
ar[i++] = j;
}
lg[0] = -1;
for (int i = 0; i < n; ++i) {
st[0][i] = i;
lg[i + 1] = lg[(i + 1) >> 1] + 1;
}
for (int j = 1; j < LG; ++j) {
for (int i = 0; i + (1 << j) - 1 < n; ++i) {
st[j][i] = ar[st[j - 1][i]] > ar[st[j - 1][i + (1 << (j - 1))]] ? st[j - 1][i] : st[j - 1][i + (1 << (j - 1))];
}
}
dfs(0, n - 1);
save_to_floppy(tr_ans);
}
string tr_val;
int ptr, cv, l[N], r[N], pos[N], vt[N], dep[N], pa[LG][N];
vector<int> v;
int dfs() {
int pp = ptr, cur = cv++;
if (tr_val[pp] == '1') {
ptr += 2;
l[cur] = dfs();
}
if (tr_val[pp + 1] == '1') {
ptr += 2;
r[cur] = dfs();
}
return cur;
}
int dfs2(int u, int k = 0) {
int ans = 1, v = 0;
if (l[u]) {
dep[l[u]] = dep[u] + 1;
pa[0][l[u]] = u;
v = dfs2(l[u], k);
k += v, ans += v;
}
for (int j = 1; j < LG; ++j) {
pa[j][u] = pa[j - 1][pa[j - 1][u]];
}
pos[u] = k, vt[k] = u;
if (r[u]) {
pa[0][r[u]] = u;
dep[r[u]] = dep[u] + 1;
ans += dfs2(r[u], k + 1);
}
return ans;
}
int lca(int u, int v) {
if (dep[v] > dep[u]) swap(u, v);
int h = dep[u] - dep[v];
for (int j = 0; j < LG; ++j) {
if ((h >> j) & 1) {
u = pa[j][u];
}
}
if (u == v) return u;
for (int j = LG - 1; j >= 0; --j) {
if (pa[j][u] != pa[j][v]) {
u = pa[j][u], v = pa[j][v];
}
}
return pa[0][u];
}
vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
vector<int> v;
tr_val = bits;
dfs();
dfs2(0);
for (int j = 1; j < LG; ++j) {
for (int u = 0; u < cv; ++u) {
pa[j][u] = pa[j - 1][pa[j - 1][u]];
}
}
int m = a.size();
vector<int> ans(m);
for (int i = 0; i < m; ++i) {
ans[i] = pos[lca(vt[a[i]], vt[b[i]])];
}
return ans;
}
Compilation message
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 |
2 ms |
796 KB |
Output is correct |
| 2 |
Correct |
3 ms |
768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
784 KB |
Output is correct |
| 4 |
Correct |
2 ms |
780 KB |
Output is correct |
| 5 |
Correct |
2 ms |
780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
4624 KB |
Output is correct |
| 2 |
Correct |
24 ms |
4636 KB |
Output is correct |
| 3 |
Correct |
25 ms |
4856 KB |
Output is correct |
| 4 |
Correct |
23 ms |
5016 KB |
Output is correct |
| 5 |
Correct |
23 ms |
4632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
17408 KB |
Output is correct |
| 2 |
Correct |
94 ms |
17368 KB |
Output is correct |
| 3 |
Correct |
95 ms |
18208 KB |
Output is correct |
| 4 |
Correct |
95 ms |
18500 KB |
Output is correct |
| 5 |
Correct |
92 ms |
17316 KB |
Output is correct |
