#include <stdio.h>
#include <ctype.h>
#include "floppy.h"
#define MAXN 40000
#define MAXL 16
std::string _out;
void dfs( int l, int r, const std::vector<int> &v ){
int i, max = l, hasleft, hasright;
char newch[3] = { '\0', '\0', '\0' };
//printf("[%d, %d]\n", l, r);
for( i = l + 1 ; i <= r ; i++ )
max = v[i] > v[max] ? i : max;
newch[0] = '0' + (hasleft = (max > l));
newch[1] = '0' + (hasright = (max < r));
_out.append(newch);
if( hasleft )
dfs(l, max - 1, v);
if( hasright )
dfs(max + 1, r, v);
}
void read_array( int subtask_id, const std::vector<int> &v ){
_out.clear();
dfs(0, v.size() - 1, v);
save_to_floppy(_out);
}
int rebuild( int v[], std::string &bits, int min, int pozv, int pozb ){
int i, hasleft, hasright, lleft, lright;
hasleft = bits[pozb ] - '0';
hasright = bits[pozb + 1] - '0';
pozb += 2;
if( hasleft ){
lleft = rebuild(v, bits, min, pozv, pozb);
min += lleft;
pozv += lleft;
pozb += 2 * lleft;
}else
lleft = 0;
i = pozv++;// retinem locul unde se afla maximul
if( hasright ){
lright = rebuild(v, bits, min, pozv, pozb);
min += lright;
}else
lright = 0;
v[i] = min;
return lleft + lright + 1;
}
int _v[MAXN];
int _n;
std::vector<int> _answers;
int _rmq[MAXN][MAXL];
int _log[MAXN + 1];
void RMQinit(){
int i, l, p2;
_log[0] = _log[1] = 0;
for( i = 2 ; i <= _n ; i++ )
_log[i] = 1 + _log[i >> 1];
for( i = 0 ; i < _n ; i++ )
_rmq[0][i] = i;
l = 1;
for( p2 = 1 ; p2 * 2 <= _n ; p2 <<= 1 ){
for( i = 0 ; i + 2 * p2 <= _n ; i++ )
_rmq[l][i] = _v[_rmq[l - 1][i]] > _v[_rmq[l - 1][i + p2]] ? _rmq[l - 1][i] : _rmq[l - 1][i + p2];
l++;
}
}
int RMQquery( int l, int r ){
int _loglr = _log[r - l + 1], p2;
p2 = (1 << _loglr);
return _v[_rmq[_loglr][l]] > _v[_rmq[_loglr][r - p2 + 1]] ? _rmq[_loglr][l] : _rmq[_loglr][r - p2 + 1];
}
std::vector<int> solve_queries( int subtask_id, int N, std::string &bits, const std::vector<int> &a, const std::vector<int> &b ){
int i;
_n = rebuild(_v, bits, 0, 0, 0);
if( _n != N ){
fprintf(stderr, "(!) CRITICAL: n not the same!!!! (%d != %d)\n", _n, N);
exit(1);
}
RMQinit();
for( i = 0 ; i < (int)a.size() ; i++ )
_answers.push_back(RMQquery(a[i], b[i]));
return _answers;
}
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/ccrBDNzd.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&)'
collect2: error: ld returned 1 exit status
