# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
858260 |
2023-10-07T18:52:12 Z |
vivo2006 |
Floppy (RMI20_floppy) |
C++14 |
|
0 ms |
0 KB |
#include<bits/stdc++.h>
#define MAXN 40004
#define INF -1e10
#include "floppy.h"
using namespace std;
vector<long long> arr;
pair<long long, long long> M[MAXN];
pair<long long, long long> cTree[MAXN];
string s;
long long ind, indexx[MAXN], done, p[MAXN][16], level[MAXN];
struct segTree
{
pair<long long, long long> tree[4 * MAXN];
void build(long long l, long long r, long long ind)
{
if(l == r)
{
tree[ind] = {arr[l], l};
return;
}
long long mid = (l + r) / 2;
build(l, mid, ind * 2 + 1);
build(mid + 1, r, ind * 2 + 2);
tree[ind] = max(tree[ind * 2 + 1], tree[ind * 2 + 2]);
}
pair<long long, long long> query(long long l, long long r, long long curL, long long curR, long long ind)
{
if(l > r) return {INF, INF};
if(curL > r || curR < l) return {INF, INF};
if(curL >= l && curR <= r) return tree[ind];
long long mid = (curL + curR) / 2;
return max(query(l, r, curL, mid, ind * 2 + 1), query(l, r, mid + 1, curR, ind * 2 + 2));
}
}st;
void buildBits(long long l, long long r, long long curInd)
{
pair<long long, long long> L = st.query(l, curInd - 1, 0, arr.size() - 1, 0);
pair<long long, long long> R = st.query(curInd + 1, r, 0, arr.size() - 1, 0);
cTree[curInd] = {INF, INF};
if(L.first != INF)
{
cTree[curInd].first = L.second;
buildBits(l, curInd - 1, L.second);
}
if(R.first != INF)
{
cTree[curInd].second = R.second;
buildBits(curInd + 1, r, R.second);
}
}
void dfs(long long v)
{
if(cTree[v].first != INF) s += "1";
else s += "0";
if(cTree[v].second != INF) s += "1";
else s += "0";
if(cTree[v].first != INF) dfs(cTree[v].first);
if(cTree[v].second != INF) dfs(cTree[v].second);
}
void read_array(long long subtask_id, const vector<int> &v)
{
arr = v;
st.build(0, v.size() - 1, 0);
buildBits(0, v.size() - 1, st.tree[0].second);
dfs(st.tree[0].second);
save_to_floppy(s);
}
void DFS(long long i)
{
done = max(done, i);
if(s[i] == '0')
{
indexx[i / 2] = ind ++;
}
else
{
DFS(i + 2);
indexx[i / 2] = ind ++;
}
if(s[i + 1] == '1')
{
DFS(done + 2);
}
}
void DFS2(long long i, long long lev)
{
done = max(done, i);
level[indexx[i / 2]] = lev;
M[indexx[i / 2]] = {INF, INF};
if(s[i] == '1')
{
M[indexx[i / 2]].first = indexx[(done + 2) / 2];
p[indexx[(done + 2) / 2]][0] = indexx[i / 2];
DFS2(i + 2, lev + 1);
}
if(s[i + 1] == '1')
{
M[indexx[i / 2]].second = indexx[(done + 2) / 2];
p[indexx[(done + 2) / 2]][0] = indexx[i / 2];
DFS2(done + 2, lev + 1);
}
}
long long solve(long long a, long long b)
{
//cout<<a<<" "<<b<<endl;
if(level[a] > level[b]) swap(a, b);
long long dif = -level[a] + level[b];
for(long long i = 0; i < 18; i ++)
{
if(dif & (1 << i))
{
b = p[b][i];
}
}
//cout<<a<<" "<<b<<endl;
if(a == b) return a;
while(p[a][0] != p[b][0])
{
long long tri = 0;
while(p[a][tri] != p[b][tri]) tri ++;
a = p[a][tri]; b = p[b][tri];
}
return p[a][0];
}
vector<int> solve_queries (int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b)
{
s = bits;
DFS(0);
done = 0;
/*for(int i = 0; i < bits.size() / 2; i ++)
{
cout<<indexx[i]<<endl;
}*/
p[0][0] = INF;
DFS2(0, 0);
vector<int> answers;
/*for(int i = 0; i < bits.size() / 2; i ++)
{
cout<<M[i].first<<" "<<M[i].second<<endl;
}*/
for(int i = 0; i < a.size(); i ++)
{
answers.push_back(solve(a[i], b[i]));
//cout<<endl;
}
return answers;
}
/*signed main()
{
vector<int> v{40, 20, 30, 10};
vector<int> a{0, 0, 0, 0, 1, 1, 1, 2, 2, 3};
vector<int> b{0, 1, 2, 3, 1, 2, 3, 2, 3, 3};
read_array(0, v);
//cout<<"effefe"<<endl;
vector<int> V = solve_queries(0, 4, s, a, b);
for(int i = 0; i < V.size(); i ++) cout<<V[i]<<endl;
}*/
Compilation message
floppy.cpp: In function 'void read_array(long long int, const std::vector<int>&)':
floppy.cpp:62:11: error: no match for 'operator=' (operand types are 'std::vector<long long int>' and 'const std::vector<int>')
62 | arr = v;
| ^
In file included from /usr/include/c++/10/vector:72,
from /usr/include/c++/10/queue:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from floppy.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
198 | vector<_Tp, _Alloc>::
| ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note: no known conversion for argument 1 from 'const std::vector<int>' to 'const std::vector<long long int>&'
199 | operator=(const vector<_Tp, _Alloc>& __x)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/queue:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from floppy.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
709 | operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note: no known conversion for argument 1 from 'const std::vector<int>' to 'std::vector<long long int>&&'
709 | operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
| ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
730 | operator=(initializer_list<value_type> __l)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note: no known conversion for argument 1 from 'const std::vector<int>' to 'std::initializer_list<long long int>'
730 | operator=(initializer_list<value_type> __l)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:141:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | 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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~