QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#623265#8783. Cherry Pickingrns_rds#WA 0ms3880kbC++232.3kb2024-10-09 10:58:152024-10-09 10:58:16

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 10:58:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3880kb
  • [2024-10-09 10:58:15]
  • 提交

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'