#include <iostream>
#include <stdlib.h>
#include <string.h>
#include "floppy.h"
using namespace std;
const int maxn = 1e5+10, maxlog = 20;
int sparse[maxlog][2*maxn], n;
int get_log[maxn];
int parent[maxn];
vector < int > g[maxn], a;
string s;
int cmp(int x, int y) {
if (a[x] > a[y]) return x;
return y;
}
int find_max(int l, int r) {
int log = get_log[r-l+1];
return cmp(sparse[log][l], sparse[log][r - (1 << log) + 1]);
}
int cnt;
void dfs(int l, int r) {
if (cnt >= n+5) return;
int mid = find_max(l, r)+1;
s[2*cnt] = s[2*cnt+1] = '1';
if (mid == l) s[2*cnt] = '0';
if (mid == r) s[2*cnt+1] = '0';
if (mid != l) {
++cnt;
dfs(l, mid-1);
}
if (mid != r) {
++cnt;
dfs(mid+1, r);
}
}
void read_array(int subtask_id, const vector < int > &v) {
a = v;
// build_sparse
n = v.size();
for (int i = 1 ; i <= n ; ++i)
sparse[0][i] = i-1;
for (int log = 1 ; (1 << log) <= n ; ++log)
for (int i = 1 ; i + (1 << log) - 1 <= n ; ++i)
sparse[log][i] = cmp(sparse[log-1][i], sparse[log-1][i + (1 << log-1)]);
for (int i = 1 ; i <= n ; ++i) {
get_log[i] = get_log[i-1];
if ((1 << get_log[i]+1) < i) ++get_log[i];
}
cnt = 0;
s.resize(2*n-2);
cnt = 0;
dfs(1, n);
save_to_floppy(s);
}
int pos[maxn], from_pos[maxn], in[maxn];
int subtree_size[maxn];
int depth[maxn];
vector < int > tour;
int cmp2(int x, int y) {
if (depth[x] < depth[y]) return x;
return y;
}
void dfs2(int parent, int addpos) {
sparse[0][cnt] = parent;
subtree_size[cnt] = 1;
depth[cnt] = depth[parent]+1;
tour.push_back(cnt);
in[cnt] = tour.size()-1;
int curr = cnt;
if (s[2*curr] == '1') {
int next = ++cnt;
dfs2(curr, addpos);
tour.push_back(curr);
subtree_size[curr] += subtree_size[next];
}
pos[curr] = subtree_size[curr] + addpos;
from_pos[pos[curr]] = curr;
if (s[2*curr+1] == '1') {
int next = ++cnt;
dfs2(curr, pos[curr]);
tour.push_back(curr);
subtree_size[curr] += subtree_size[next];
}
}
int query(int l, int r) {
int log = get_log[r-l+1];
return cmp2(sparse[log][l], sparse[log][r - (1 << log) + 1]);
}
vector< int > solve_queries(int subtask_id, int N, const string &bits, const vector < int > &a, const vector < int > &b) {
s = bits;
cnt = 0;
dfs2(0, 0);
vector < int > ans;
for (int i = 0 ; i < tour.size() ; ++i)
sparse[0][i] = tour[i];
for (int log = 1 ; (1 << log) <= tour.size() ; ++log)
for (int i = 0 ; i + (1 << log) - 1 < tour.size() ; ++i)
sparse[log][i] = cmp2(sparse[log-1][i], sparse[log-1][i + (1 << log-1)]);
for (int i = 1 ; i <= tour.size() ; ++i) {
get_log[i] = get_log[i-1];
if ((1 << get_log[i]+1) < i) ++get_log[i];
}
for (int i = 0 ; i < a.size() ; ++i) {
ans.push_back(pos[query(in[from_pos[a[i]+1]], in[from_pos[b[i]+1]])]-1);
}
return ans;
}
/*
3 4 9
40 20 30 10
0 3 0
0 1 0
2 3 2
1 3 2
1 2 2
2 3 2
1 1 1
3 3 3
0 2 0
3 4 1
40 20 30 10
1 1 1
*/
Compilation message
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:69:79: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
69 | sparse[log][i] = cmp(sparse[log-1][i], sparse[log-1][i + (1 << log-1)]);
| ~~~^~
floppy.cpp:74:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
74 | if ((1 << get_log[i]+1) < i) ++get_log[i];
| ~~~~~~~~~~^~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:146:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int i = 0 ; i < tour.size() ; ++i)
| ~~^~~~~~~~~~~~~
floppy.cpp:149:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for (int log = 1 ; (1 << log) <= tour.size() ; ++log)
| ~~~~~~~~~~~^~~~~~~~~~~~~~
floppy.cpp:150:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for (int i = 0 ; i + (1 << log) - 1 < tour.size() ; ++i)
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
floppy.cpp:151:80: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
151 | sparse[log][i] = cmp2(sparse[log-1][i], sparse[log-1][i + (1 << log-1)]);
| ~~~^~
floppy.cpp:153:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for (int i = 1 ; i <= tour.size() ; ++i) {
| ~~^~~~~~~~~~~~~~
floppy.cpp:156:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
156 | if ((1 << get_log[i]+1) < i) ++get_log[i];
| ~~~~~~~~~~^~
floppy.cpp:160:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | 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 |
4 ms |
5524 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5664 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5532 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5664 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5664 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
24 ms |
9260 KB |
Output is correct |
| 2 |
Correct |
25 ms |
9264 KB |
Output is correct |
| 3 |
Correct |
25 ms |
9632 KB |
Output is correct |
| 4 |
Correct |
24 ms |
9436 KB |
Output is correct |
| 5 |
Correct |
25 ms |
9312 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
91 ms |
21700 KB |
Output is correct |
| 2 |
Correct |
101 ms |
21780 KB |
Output is correct |
| 3 |
Correct |
94 ms |
22940 KB |
Output is correct |
| 4 |
Correct |
91 ms |
22452 KB |
Output is correct |
| 5 |
Correct |
84 ms |
21656 KB |
Output is correct |
