QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#682076#8783. Cherry Pickingi_am_noob#WA 1ms3636kbC++142.0kb2024-10-27 13:45:572024-10-27 13:45:57

Judging History

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

  • [2024-10-27 13:45:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3636kb
  • [2024-10-27 13:45:57]
  • 提交

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";
}

詳細信息

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'