#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
#define isz(a) (int)(a).size()
const int NM = 4e4, LOG = 15;
int N, a[NM+5];
int f[LOG+5][NM+5];
string s;
int ptr = 0, d[NM+5], sz[NM+5];
void build_sparse(){
for (int i = 1; i <= N; i++) f[0][i] = i;
for (int i = 1; i <= LOG; i++)
for (int j = 1; j+(1<<i)-1 <= N; j++){
int x = f[i-1][j], y = f[i-1][j+(1<<(i-1))];
if (a[x] > a[y]) f[i][j] = x; else f[i][j] = y;
}
}
int get(int l, int r){
int i = __lg(r-l+1), x = f[i][l], y = f[i][r-(1<<i)+1];
if (a[x] > a[y]) return x;
return y;
}
void dnc(int l, int r){
if (l > r) return;
if (l == r){
s.push_back('0');
s.push_back('0');
return;
}
int mid = get(l, r);
if (mid > l) s.push_back('1'); else s.push_back('0');
if (mid < r) s.push_back('1'); else s.push_back('0');
dnc(l, mid-1);
dnc(mid+1, r);
}
void read_array(int subtask_id, const vector<int> &v) {
N = isz(v);
for (int i = 1; i <= N; i++) a[i] = v[i-1];
build_sparse();
dnc(1, N);
save_to_floppy(s);
}
void dfs(int u){
sz[u] = 1;
d[u] = 0;
if (s[2*u] == '1'){
ptr += 2;
int v = ptr/2;
dfs(v);
sz[u] += sz[v];
d[u] = max(d[u], d[v]+1);
}
if (s[2*u+1] == '1'){
ptr += 2;
int v = ptr/2;
dfs(v);
sz[u] += sz[v];
d[u] = max(d[u], d[v]+1);
}
}
void restore(int u, int l, int r){
int mid = (s[ptr] == '1' ? l+sz[u+1] : l);
a[mid] = d[u];
if (s[2*u] == '1'){
ptr += 2;
restore(ptr/2, l, mid-1);
}
if (s[2*u+1] == '1'){
ptr += 2;
restore(ptr/2, mid+1, r);
}
}
vector<int> solve_queries(int subtask_id, int _N, const string &bits, const vector<int> &l, const vector<int> &r) {
s = bits;
N = _N;
dfs(0);
ptr = 0;
restore(0, 1, N);
build_sparse();
vector <int> ans(isz(l));
for (int i = 0; i < isz(l); i++){
ans[i] = get(l[i]+1, r[i]+1)-1;
}
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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4916 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5028 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4988 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4976 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
7612 KB |
Output is correct |
| 2 |
Correct |
16 ms |
7612 KB |
Output is correct |
| 3 |
Correct |
17 ms |
7844 KB |
Output is correct |
| 4 |
Correct |
16 ms |
7872 KB |
Output is correct |
| 5 |
Correct |
18 ms |
7612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
16672 KB |
Output is correct |
| 2 |
Correct |
64 ms |
17040 KB |
Output is correct |
| 3 |
Correct |
66 ms |
17724 KB |
Output is correct |
| 4 |
Correct |
67 ms |
17960 KB |
Output is correct |
| 5 |
Correct |
71 ms |
16800 KB |
Output is correct |
