| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 924227 |
2024-02-08T16:39:13 Z |
vjudge1 |
Floppy (RMI20_floppy) |
C++17 |
|
136 ms |
33120 KB |
#include<bits/stdc++.h>
#include "floppy.h"
using namespace std;
template<class T, class F>
struct sparse_table{
int n;
vector<vector<T>> data;
F TT;
T T_id;
sparse_table(){ }
// O(n log n)
sparse_table(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id), data({a}){
for(auto p = 1, i = 1; p << 1 <= n; p <<= 1, ++ i){
data.emplace_back(n - (p << 1) + 1);
for(auto j = 0; j < (int)data[i].size(); ++ j) data[i][j] = TT(data[i - 1][j], data[i - 1][j + p]);
}
}
// O(1)
T query(int l, int r) const{
assert(0 <= l && l <= r && r <= n);
if(l == r) return T_id;
int d = __lg(r - l);
return TT(data[d][l], data[d][r - (1 << d)]);
}
};
pair<int, int> op(pair<int, int> a, pair<int, int> b) { return max(a, b); }
void read_array(int subtask_id, const std::vector<int> &v) {
int n = (int)(v.size());
vector<pair<int, int>> a(n);
for (int i = 0; i < n; ++i) a[i] = {v[i], i};
sparse_table st(a, op, pair{0, 0});
vector<vector<int>> G(n);
auto dfs = [&](auto self, int l, int r) -> int {
if (l == r) return ~l;
int pos = st.query(l, r).second;
G[pos].emplace_back(self(self, l, pos));
G[pos].emplace_back(self(self, pos + 1, r));
return pos;
};
int root = dfs(dfs, 0, n);
auto dfs2 = [&](auto self, int v) -> pair<int, string> {
vector<pair<int, string>> vec;
for (int u : G[v]) {
if (u < 0) vec.emplace_back(u, "");
else vec.push_back(self(self, u));
}
sort(vec.rbegin(), vec.rend());
if (vec[0].second.empty() and vec[1].second.empty()) return {vec[0].first, "01"};
if (vec[0].second.empty()) return {vec[0].first, "0" + vec[1].second + "1"};
if (vec[1].second.empty()) return {vec[0].first, vec[0].second + "01"};
return {vec[0].first, vec[0].second + "0" + vec[1].second + "1"};
};
save_to_floppy(dfs2(dfs2, root).second);
}
std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
int n = (int)(bits.size()) / 2;
vector<pair<int, int>> aa(n);
for (int i = 0; i < n; ++i) aa[i].second = i;
vector<int> posge(2 * n, -1);
map<int, vector<int>> premp;
int csum = 0;
for (int i = 0; i < 2 * n; ++i) {
if (bits[i] == '0') {
premp[csum++].emplace_back(i);
}
else {
csum--;
int other = premp[csum].back();
posge[other] = i, posge[i] = other;
premp[csum].pop_back();
}
}
// cerr << bits << endl;
auto dfs = [&](auto self, int posl, int posr, int l, int r, int l1, int r1) -> void {
// cout << "dfs: " << posl << " " << posr << " " << l << " " << r << " " << l1 << " " << r1 << endl;
int len = posr - posl + 1, sum = 0, pos = posge[posr];
if (len == 2) {
aa[l].first = r1;
return;
}
assert(pos != -1);
if (pos == posl) {
aa[l].first = r1;
self(self, posl + 1, posr - 1, l + 1, r, l1, r1 - 1);
}
else if (pos == posr - 1) {
aa[r].first = r1;
self(self, posl, posr - 2, l, r - 1, l1, r1 - 1);
}
else {
int inter = l + (pos - posl) / 2;
aa[inter].first = r1;
self(self, posl, pos - 1, l, inter - 1, l1, l1 + (pos - posl) / 2 - 1);
self(self, pos + 1, posr - 1, inter + 1, r, l1 + (pos - posl) / 2, r1 - 1);
}
};
dfs(dfs, 0, 2 * n - 1, 0, n - 1, 0, n - 1);
sparse_table st(aa, op, pair{0, 0});
vector<int> answers((int)(a.size()));
for (int i = 0; i < (int)(a.size()); ++i) {
answers[i] = st.query(a[i], b[i] + 1).second;
}
return answers;
}
Compilation message
floppy.cpp: In instantiation of 'sparse_table<T, F>::sparse_table(const std::vector<_Tp>&, F, T) [with T = std::pair<int, int>; F = std::pair<int, int> (*)(std::pair<int, int>, std::pair<int, int>)]':
floppy.cpp:35:38: required from here
floppy.cpp:11:7: warning: 'sparse_table<std::pair<int, int>, std::pair<int, int> (*)(std::pair<int, int>, std::pair<int, int>)>::T_id' will be initialized after [-Wreorder]
11 | T T_id;
| ^~~~
floppy.cpp:9:23: warning: 'std::vector<std::vector<std::pair<int, int> >, std::allocator<std::vector<std::pair<int, int> > > > sparse_table<std::pair<int, int>, std::pair<int, int> (*)(std::pair<int, int>, std::pair<int, int>)>::data' [-Wreorder]
9 | vector<vector<T>> data;
| ^~~~
floppy.cpp:14:5: warning: when initialized here [-Wreorder]
14 | sparse_table(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id), data({a}){
| ^~~~~~~~~~~~
floppy.cpp: In instantiation of 'solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)::<lambda(auto:25, int, int, int, int, int, int)> [with auto:25 = solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)::<lambda(auto:25, int, int, int, int, int, int)>]':
floppy.cpp:103:46: required from here
floppy.cpp:82:36: warning: unused variable 'sum' [-Wunused-variable]
82 | int len = posr - posl + 1, sum = 0, pos = posge[posr];
| ^~~
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 |
1 ms |
824 KB |
Output is correct |
| 2 |
Correct |
1 ms |
828 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1084 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
6080 KB |
Output is correct |
| 2 |
Correct |
20 ms |
6076 KB |
Output is correct |
| 3 |
Correct |
24 ms |
8380 KB |
Output is correct |
| 4 |
Correct |
23 ms |
7308 KB |
Output is correct |
| 5 |
Correct |
21 ms |
5984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
23844 KB |
Output is correct |
| 2 |
Correct |
83 ms |
24024 KB |
Output is correct |
| 3 |
Correct |
136 ms |
33120 KB |
Output is correct |
| 4 |
Correct |
115 ms |
27828 KB |
Output is correct |
| 5 |
Correct |
80 ms |
23660 KB |
Output is correct |
