QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#682076 | #8783. Cherry Picking | i_am_noob# | WA | 1ms | 3636kb | C++14 | 2.0kb | 2024-10-27 13:45:57 | 2024-10-27 13:45:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define sz(a) ((int)a.size())
#define pb push_back
#define all(a) a.begin(),a.end()
const int N=100005;
int n,k,a[N];
string s;
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> n >> k;
for(int i=0; i<n; ++i) cin >> a[i];
cin >> s;
set<array<int,4>> st;
int cur=0;
for(int i=0; i<n; ++i){
if(i>0&&s[i]!=s[i-1]){
st.insert({cur,i-1,s[cur]-'0',i-cur});
cur=i;
}
}
st.insert({cur,n-1,s[cur]-'0',n-cur});
int res=0,cnt=0;
for(auto &[l,r,t,x]: st) if(t==1&&x>=k) cnt++;
vector<int> ord(n); iota(all(ord),0);
sort(all(ord),[&](int i, int j){return a[i]<a[j];});
if(cnt) res=max(res,a[ord[0]]);
for(int i=0; i<n-1; ++i){
//cout << i << ' ' << ord[i] << "\n";
//for(auto &[l,r,t,x]: st) cout << l << ' ' << r << ' ' << t << ' ' << x << "\n";
//cout << cnt << "\n";
int j=ord[i];
int mx=1e9;
auto it=st.lower_bound({j,mx,mx,mx});
it--;
if((*it)[2]==1&&(*it)[3]==k) cnt--;
auto arr=*it;
arr[3]--;
if(arr[3]){
st.erase(it);
st.insert(arr);
if(cnt&&a[ord[i+1]]>a[ord[i]]) res=max(res,a[ord[i+1]]);
continue;
}
if(next(it)!=st.end()&&it!=st.begin()){
it=prev(it);
st.erase(next(it));
arr=*it;
arr[1]=(*next(it))[1];
if(arr[1]==1){
if(arr[3]>=k) cnt--;
if((*next(it))[3]>=k) cnt--;
}
arr[3]+=(*next(it))[3];
if(arr[1]==1){
if(arr[3]>=k) cnt++;
}
st.erase(next(it));
st.erase(it);
st.insert(arr);
}
else{
st.erase(it);
}
if(cnt&&a[ord[i+1]]>a[ord[i]]) res=max(res,a[ord[i+1]]);
}
cout << res << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3616kb
input:
5 2 1 2 3 4 5 01101
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
5 2 3 4 5 2 1 10101
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
1 1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1 1 1 0
output:
0
result:
ok answer is '0'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3636kb
input:
5 3 8 3 5 2 7 10101
output:
8
result:
wrong answer expected '5', found '8'