#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include "floppy.h"
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>
#define fr first
#define sc second
using namespace std;
#define NMAX 100000
#define MMAX 100000
int leftc[NMAX], rightc[NMAX];
int par[18][NMAX], depth[NMAX];
int timer = 0;
void dfs_1(int u, const string &bits)
{
//cout << "AT NODE " << u << endl;
if(bits[2*u] == '1')
{
int new_node = ++timer;
par[0][new_node] = u;
leftc[u] = new_node;
depth[new_node] = depth[u]+1;
//cout << "GO TO NODE " << new_node << endl;
dfs_1(new_node, bits);
}
if(bits[2*u+1] == '1')
{
int new_node = ++timer;
par[0][new_node] = u;
rightc[u] = new_node;
depth[new_node] = depth[u]+1;
//cout << "GO TO NODE " << new_node << endl;
dfs_1(new_node, bits);
}
}
int jump(int a, int l)
{
for(int i = 0; i < 18; i++)
{
if((l&(1<<i)) != 0)
{
a = par[i][a];
}
}
return a;
}
int lca(int a, int b)
{
if(depth[a] < depth[b])
{
swap(a, b);
}
a = jump(a, depth[a]-depth[b]);
if(a == b)
{
return a;
}
for(int i = 17; i >= 0; i--)
{
if(par[i][a] != par[i][b])
{
a = par[i][a];
b = par[i][b];
}
}
return par[0][a];
}
int trans[NMAX], inv_trans[NMAX];
int code = 0;
void dfs_2(int u)
{
if(leftc[u] != -1)
{
dfs_2(leftc[u]);
}
trans[u] = code;
inv_trans[code] = u;
code++;
if(rightc[u] != -1)
{
dfs_2(rightc[u]);
}
}
vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b)
{
for(int i = 0; i <= n; i++)
{
leftc[i] = -1;
rightc[i] = -1;
par[0][i] = -1;
}
dfs_1(0, bits);
for(int i = 1; i <= 17; i++)
{
for(int j = 0; j < n; j++)
{
par[i][j] = par[i-1][par[i-1][j]];
}
}
dfs_2(0);
vector<int> answers;
for(int i = 0; i < a.size(); i++)
{
answers.push_back(trans[lca(inv_trans[a[i]], inv_trans[b[i]])]);
}
return answers;
}
void read_array(int subtask_id, const vector<int> &v)
{
int n = v.size();
int rc[n], lc[n], p[n];
for(int i = 0; i < n; i++)
{
rc[i] = -1;
lc[i] = -1;
p[i] = -1;
}
int root = 0;
for(int i = 1; i < n; i++)
{
int last_val = i-1;
while(last_val != -1)
{
if(-v[last_val] < -v[i])
{
lc[i] = rc[last_val];
rc[last_val] = i;
p[i] = last_val;
p[lc[i]] = i;
break;
}
last_val = p[last_val];
}
if(last_val == -1)
{
lc[i] = root;
p[root] = i;
root = i;
}
}
string bits = "";
stack<int> s;
s.push(root);
while(!s.empty())
{
int nw = s.top();
s.pop();
string bruh = "00";
if(rc[nw] != -1)
{
bruh[1] = '1';
s.push(rc[nw]);
}
if(lc[nw] != -1)
{
bruh[0] = '1';
s.push(lc[nw]);
}
bits+=bruh;
}
//cout << bits << endl;
save_to_floppy(bits);
}
/*
3
4 10
40 20 30 10
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3
3
11 5
21 27 23 29 22 18 20 10 15 12 25
0 2 1
2 6 3
0 10 3
7 9 8
7 7 7
*/
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/
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:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | 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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
9000 KB |
Output is correct |
2 |
Correct |
1 ms |
9008 KB |
Output is correct |
3 |
Correct |
2 ms |
9008 KB |
Output is correct |
4 |
Correct |
2 ms |
9000 KB |
Output is correct |
5 |
Correct |
1 ms |
9000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
11052 KB |
Output is correct |
2 |
Correct |
13 ms |
11052 KB |
Output is correct |
3 |
Correct |
12 ms |
11176 KB |
Output is correct |
4 |
Correct |
13 ms |
11328 KB |
Output is correct |
5 |
Correct |
12 ms |
11056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
17208 KB |
Output is correct |
2 |
Correct |
50 ms |
17284 KB |
Output is correct |
3 |
Correct |
50 ms |
17144 KB |
Output is correct |
4 |
Correct |
52 ms |
17664 KB |
Output is correct |
5 |
Correct |
49 ms |
17128 KB |
Output is correct |