QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#623270#8783. Cherry Pickingrns_rds#WA 1ms3808kbC++232.3kb2024-10-09 11:00:492024-10-09 11:00:49

Judging History

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

  • [2024-10-09 11:00:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3808kb
  • [2024-10-09 11:00:49]
  • 提交

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'