QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#621475#8783. Cherry Pickingucup-team2526WA 1ms5704kbC++202.6kb2024-10-08 14:45:402024-10-08 14:46:41

Judging History

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

  • [2024-10-08 14:46:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5704kb
  • [2024-10-08 14:45:40]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;

#define dbg(x...) \
do { \
    cout << #x << " -> "; \
    err(x); \
} while (0)

void err() {
    cout<<endl<<endl;
}
 
template<class T, class... Ts>
void err(T arg, Ts ... args) {
    cout<<fixed<<setprecision(10)<<arg<< ' ';
    err(args...);
}

const int maxn = 1e5 + 5;
struct BIT {
    #define lowbit(x) (x&(-x))
    int tr[maxn << 2];
    void add(int u,int v) {
        while (u <= maxn) {
            tr[u] += v;
            u += lowbit(u);
        }
    }
    int get(int u) {
        int res = 0;
        while (u) {
            res += tr[u];
            u -= lowbit(u);
        }
        return res;
    }
}bit;

void solve(){
    int n,k;cin >> n >> k;
    vector<int> a(n + 5);
    for (int i = 1;i <= n;i++) cin >> a[i];
    string res;cin >> res;
    int l = -1,r = -1;
    int cnt = 1,ans = 0;
    for (int i = 1;i <= n;i++) {
        if (res[i - 1] == '1') {
            bit.add(a[i],1);
            l = i,r = i;
            if (k == 1) ans = max(ans,a[i]);
            break;
        }
    }
    //dbg(l,r);
    if (l == -1) {
        cout << 0 << '\n';
        return ;
    }
    multiset<int>s0,s1;
    s1.insert(a[l]);
    while (1) {
        int ok = 0;
        for (int i = r + 1;i <= n;i++) {
            if (res[i - 1] == '0') {
                s0.insert(a[i]);
            }
            else {
                cnt++;
                bit.add(a[i],1);
                s1.insert(a[i]);
                if (cnt >= k) {
                    int mi0;
                    if (s0.empty()) mi0 = 0;
                    else mi0 = *(s0.rbegin());
                    int num = bit.get(mi0);
                    if (cnt - num >= k) {
                        ok = 1;
                        auto it = s1.lower_bound(mi0 + 1);
                        int val = *(it);
                        ans = max(ans,val);
                        r = i;
                        break;
                    }
                }
            }
        }
        if (!ok) break;
        bit.add(a[l],-1);
        cnt--;
        s1.erase(s1.find(a[l]));
        for (int i = l + 1;i <= n;i++) {
            if (res[i - 1] == '0') s0.erase(s0.find(a[i]));
            else {
                l = i;
                ok = 0;
                break;
            }
        }
        if (ok) break;
    }
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while(T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3676kb

input:

5 2
1 2 3 4 5
01101

output:

2

result:

ok answer is '2'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

5 2
3 4 5 2 1
10101

output:

0

result:

ok answer is '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

1 1
1
1

output:

1

result:

ok answer is '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

1 1
1
0

output:

0

result:

ok answer is '0'

Test #5:

score: 0
Accepted
time: 1ms
memory: 5704kb

input:

5 3
8 3 5 2 7
10101

output:

5

result:

ok answer is '5'

Test #6:

score: 0
Accepted
time: 1ms
memory: 5704kb

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: 1ms
memory: 5640kb

input:

10 1
6 7 2 10 8 4 4 9 7 9
0111011000

output:

10

result:

ok answer is '10'

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 3832kb

input:

10 2
4 5 9 6 9 10 6 9 2 7
1100010100

output:

4

result:

wrong answer expected '9', found '4'