QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#623270 | #8783. Cherry Picking | rns_rds# | WA | 1ms | 3808kb | C++23 | 2.3kb | 2024-10-09 11:00:49 | 2024-10-09 11:00:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct RMQ { // 0-index
int sz;
vector<vector<int>> d1, d2;
RMQ(){};
RMQ(vector<int> _init) { init(_init); }
void init(vector<int> _init) {
sz = _init.size();
d1.resize(sz, vector<int>(21));
d2.resize(sz, vector<int>(21));
auto build = [&]() {
for (int i = 0; i < sz; i++)
d1[i][0] = d2[i][0] = _init[i];
for (int k = 1; k < 21; k++) {
for (int i = 0; i < sz; i++) {
d1[i][k] = d1[i][k - 1];
d2[i][k] = d2[i][k - 1];
if (i + (1 << k - 1) < sz) {
d1[i][k] = max(d1[i][k], d1[i + (1 << k - 1)][k - 1]);
d2[i][k] = min(d2[i][k], d2[i + (1 << k - 1)][k - 1]);
}
}
}
};
build();
}
int query_max(int l, int r) { // [l, r)
int k = 31 - __builtin_clz(r - l);
return max(d1[l][k], d1[r - (1 << k)][k]);
}
int query_min(int l, int r) { // [l, r)
int k = 31 - __builtin_clz(r - l);
return min(d2[l][k], d2[r - (1 << k)][k]);
}
};
void solve() {
const int inf = 1e+8;
int n, k;
cin >> n >> k;
vector<int> a(n), b(n), c(n), pos;
for (int i = 0; i < n; i++)
cin >> a[i];
string s;
cin >> s;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
b[i] = a[i];
c[i] = inf;
} else {
b[i] = 0;
c[i] = a[i];
pos.push_back(i);
}
}
// for (auto e : b)
// cout << e << ' ';
// cout << endl;
// for (auto e : c)
// cout << e << ' ';
// cout << endl;
RMQ rmq1(b), rmq2(c);
int ans = 0;
// for (auto e : pos)
// cout << e << ' ';
// cout << endl;
bool flag = false;
for (int i = 0; i + k <= pos.size(); i++) {
int l = pos[i], r = pos[i + k - 1];
int mn = rmq2.query_min(l, r);
int mx = rmq1.query_max(l, r);
if (mn > mx) {
ans = max(ans, mn);
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3808kb
input:
5 2 1 2 3 4 5 01101
output:
2
result:
ok answer is '2'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3620kb
input:
5 2 3 4 5 2 1 10101
output:
5
result:
wrong answer expected '0', found '5'