#include <bits/stdc++.h>
#include "floppy.h"
#define pii pair<int, int>
#define ll long long
#define oo 2e9
using namespace std;
const int MAX = 4e4 + 4, LOGMAX = 20;
int n;
int nxt = 0;
int arr[MAX];
pii tree[4 * MAX];
string bits;
void build(int node, int l, int r){
if(l == r){
tree[node] = {arr[l], l};
return;
}
int mid = (l + r) / 2;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
pii ask(int node, int l, int r, int ql, int qr){
if(r < ql || qr < l){
return {0, 0};
}
if(ql <= l && r <= qr){
return tree[node];
}
int mid = (l + r) / 2;
return max(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
}
void rec(int l, int r){
int m = ask(1, 1, n, l, r).second;
int i = nxt++;
if(l <= m - 1){
bits[2 * i] = '1';
rec(l, m - 1);
}
if(r >= m + 1){
bits[2 * i + 1] = '1';
rec(m + 1, r);
}
}
void read_array(int subtask_id, const std::vector<int> &v) {
n = v.size();
for(int i = 0; i < n; i++){
arr[i + 1] = v[i] + 1e9 + 100;
}
build(1, 1, n);
bits.resize(2 * n, '0');
rec(1, n);
save_to_floppy(bits);
}
int L[MAX], R[MAX];
int par[LOGMAX][MAX], timeIn[MAX], timeOut[MAX], sub[MAX];
void rec(int node, const string& bits){
if(bits[2 * node] == '1'){
L[node] = nxt++;
rec(L[node], bits);
}
if(bits[2 * node + 1] == '1'){
R[node] = nxt++;
rec(R[node], bits);
}
}
void calcSub(int node){
sub[node] = 1;
if(L[node]){
calcSub(L[node]);
sub[node] += sub[L[node]];
}
if(R[node]){
calcSub(R[node]);
sub[node] += sub[R[node]];
}
}
int t = 1;
void dfs(int node, int ad, int p){
int a = sub[L[node]] + ad;
timeIn[a] = t++;
par[0][a] = p;
if(node == 0){
par[0][a] = a;
}
if(L[node]){
dfs(L[node], ad, a);
}
if(R[node]){
dfs(R[node], ad + sub[L[node]] + 1 , a);
}
timeOut[a] = t++;
}
bool isAnc(int u, int v){
return timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v];
}
int LCA(int u, int v){
if(isAnc(u, v)) return u;
if(isAnc(v, u)) return v;
for(int j = LOGMAX - 1; j >= 0; j--){
if(!isAnc(par[j][u], v)){
u = par[j][u];
}
}
return par[0][u];
}
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
n = N;
nxt = 1;
rec(0, bits);
calcSub(0);
sub[0] = 0;
dfs(0, 0, 0);
for(int j = 1; j < LOGMAX; j++){
for(int i = 0; i < n; i++){
par[j][i] = par[j - 1][par[j - 1][i]];
}
}
vector<int> ans;
for(int i = 0; i < a.size(); i++){
ans.push_back(LCA(a[i], b[i]));
}
return ans;
}
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:140:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int i = 0; i < a.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 |
2 ms |
6960 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6960 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6952 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6952 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
8756 KB |
Output is correct |
| 2 |
Correct |
19 ms |
8748 KB |
Output is correct |
| 3 |
Correct |
18 ms |
9272 KB |
Output is correct |
| 4 |
Correct |
20 ms |
9112 KB |
Output is correct |
| 5 |
Correct |
22 ms |
8752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
15184 KB |
Output is correct |
| 2 |
Correct |
78 ms |
15116 KB |
Output is correct |
| 3 |
Correct |
78 ms |
16788 KB |
Output is correct |
| 4 |
Correct |
81 ms |
15944 KB |
Output is correct |
| 5 |
Correct |
78 ms |
15328 KB |
Output is correct |
