#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
/*
#define cin fin
#define cout fout
string __fname = ""; ifstream fin(__fname + ".in"); ofstream fout(__fname + ".out");
*/
#define ull unsigned long long
#define ll long long
#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 4e4 + 100;
#include "floppy.h"
struct segtree{
struct item{
int val = 0;
int lazy = 0;
};
// const item DEFAULT = {0, 1, 0};
vector<int> s;
int size = 0;
// void apply(int x, int val){
// // s[x].val += val;
// // s[x].lazy += val;
// }
// void push(int x){
// // if(s[x].lazy != 0){
// // apply(2 * x + 1, s[x].lazy);
// // apply(2 * x + 2, s[x].lazy);
// // s[x].lazy = 0;
// // }
// }
// void merge(int x, vector<int> & a){
// if(a[s[2 * x + 1]] > a[s[2 * x + 2]])
// s[x] = s[2 * x + 1];
// else
// s[x] = s[2 * x + 2];
// }
void build_tree(int x, int l, int r, vector<int> & a){
if(l == r){
s[x] = l;
return;
}
int mid = (l + r) >> 1;
build_tree(2 * x + 1, l, mid, a);
build_tree(2 * x + 2, mid+1, r, a);
s[x] = (a[s[2 * x + 1]] > a[s[2 * x + 2]]) ? s[2 * x + 1] : s[2 * x + 2];
}
void build_tree(vector<int> & a){
size = a.size();
s.resize(4 * size);
build_tree(0, 0, size - 1, a);
}
int query(int x, int lx, int rx, int l, int r, vector<int> & a){
if(l > r)
return -1;
if(l <= lx && rx <= r)
return s[x];
// push(x);
int mid = (lx + rx) >> 1;
int s1 = query(2 * x + 1, lx, mid, l, min(r, mid), a);
int s2 = query(2 * x + 2, mid+1, rx, max(l, mid+1), r, a);
if(s1 == -1 && s2 == s1)
return -1;
if(s1 == -1)
return s2;
if(s2 == -1)
return s1;
if(a[s1] > a[s2])
return s1;
return s2;
}
int query(int l, int r, vector<int> & a){
return query(0, 0, size-1, l, r, a);
}
} st1, st2;
string res_bits;
void encode(int l, int r, vector<int> & a){
if(l > r)
return;
if(l == r){
res_bits += "00";
return;
}
int mid = st1.query(l, r, a);
if(mid == l){
res_bits += "01";
encode(mid + 1, r, a);
}
else if(mid == r){
res_bits += "10";
encode(l, mid - 1, a);
}
else{
res_bits += "11";
encode(l, mid - 1, a);
encode(mid + 1, r, a);
}
}
void read_array(int subtask_id, vector<int> &v){
int n = v.size();
st1.build_tree(v);
encode(0, n - 1, v);
save_to_floppy(res_bits);
}
int idx = 0;
vector<int> szl;
void dfs(string bits){
bool l = (bits[2 * idx] == '1'), r = (bits[2 * idx + 1] == '1');
if(!l && !r)
return;
int old_idx = idx;
idx++;
dfs(bits);
if(!l)
return;
if(!r){
szl[old_idx] = idx - old_idx;
return;
}
szl[old_idx] = idx - old_idx;
//old_idx = idx;
idx++;
dfs(bits);
//
}
vector<int> ar;
int val;
void decode(int idx, int l, int r){
if(l > r)
return;
if(l == r){
ar[l] = val;
val--;
return;
}
int mid = l + szl[idx];
ar[mid] = val;
val--;
decode(idx + 1, l, mid - 1);
decode(idx + szl[idx] + 1, mid + 1, r);
}
vector<int> solve_queries(int sub, int n, string bits, vector<int> l, vector<int> r){
int q = l.size();
vector<int> ans;
szl = vector<int> (n);
dfs(bits);
// for(auto i : szl)
// cout << i << ' ';
// cout << '\n';
ar = vector<int> (n);
val = n - 1;
decode(0, 0, n - 1);
// for(auto i : ar)
// cout << i << ' ';
// cout << '\n';
st2.build_tree(ar);
for(int i = 0; i < q; i++)
ans.push_back(st2.query(l[i], r[i], ar));
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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
/usr/bin/ld: /tmp/ccNq8kM4.o: in function `run2()':
stub.cpp:(.text+0x698): undefined reference to `solve_queries(int, int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::vector<int, std::allocator<int> > const&, std::vector<int, std::allocator<int> > const&)'
/usr/bin/ld: /tmp/ccNq8kM4.o: in function `run1()':
stub.cpp:(.text+0xb1d): undefined reference to `read_array(int, std::vector<int, std::allocator<int> > const&)'
collect2: error: ld returned 1 exit status
