QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#623265 | #8783. Cherry Picking | rns_rds# | WA | 0ms | 3880kb | C++23 | 2.3kb | 2024-10-09 10:58:15 | 2024-10-09 10:58:16 |
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] + 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: 0ms
memory: 3772kb
input:
5 2 1 2 3 4 5 01101
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
5 2 3 4 5 2 1 10101
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
1 1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
1 1 1 0
output:
0
result:
ok answer is '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
5 3 8 3 5 2 7 10101
output:
5
result:
ok answer is '5'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
10 3 1 10 2 3 9 3 1 6 9 3 1100110001
output:
0
result:
ok answer is '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
10 1 6 7 2 10 8 4 4 9 7 9 0111011000
output:
10
result:
ok answer is '10'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
10 2 4 5 9 6 9 10 6 9 2 7 1100010100
output:
9
result:
ok answer is '9'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
10 3 2 10 8 5 8 3 7 9 9 1 1100011100
output:
3
result:
ok answer is '3'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
10 5 5 5 9 2 7 2 4 8 4 8 1010001100
output:
0
result:
ok answer is '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
10 10 6 5 8 3 2 8 6 4 5 5 0111001100
output:
0
result:
ok answer is '0'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
100 1 13 90 87 79 34 66 76 58 65 37 63 38 84 88 89 98 63 55 16 39 64 50 28 64 4 69 40 51 75 37 11 9 20 29 36 29 30 61 38 54 92 78 72 36 78 24 78 8 98 11 2 41 64 51 45 67 27 80 67 84 73 50 99 82 39 70 84 18 54 43 85 96 59 98 82 5 57 46 68 31 97 89 21 65 57 37 58 25 30 40 15 76 44 85 75 65 22 97 93 82...
output:
97
result:
ok answer is '97'
Test #13:
score: -100
Wrong Answer
time: 0ms
memory: 3880kb
input:
100 2 91 44 64 58 26 25 62 97 13 27 8 49 93 15 43 16 8 96 98 48 43 7 41 81 61 90 10 69 49 24 48 22 32 59 10 67 45 54 53 47 47 71 48 48 18 42 45 17 42 96 23 37 2 38 66 22 31 83 89 23 51 81 56 71 58 61 22 67 41 58 93 67 90 58 65 50 64 1 12 58 25 20 81 25 99 87 72 63 42 51 80 93 42 1 22 99 38 66 59 87 ...
output:
90
result:
wrong answer expected '93', found '90'