QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#556835#8783. Cherry PickingHTensorWA 2ms7068kbC++172.5kb2024-09-10 21:19:522024-09-10 21:19:52

Judging History

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

  • [2024-09-10 21:19:52]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7068kb
  • [2024-09-10 21:19:52]
  • 提交

answer

#include <bits/stdc++.h>
#define dd(x) cout << #x << "\n"
#define d(x) cout << #x  << ": " << x << "\n"
using namespace std;
#define int long long
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using a3 = array<int, 3>;
const int inf = 0x3f3f3f3f3f3f3f3fLL;

class DSU {
public:
    vector<int> fa, cnt;
    multiset<int> s;
    DSU(int n) : fa(n + 1), cnt(n + 1) {
        iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
    void merge(int a, int b) {
        int x = find(a), y = find(b); 
        if(x == y) return ;
        if(x > y) swap(x, y);
        s.erase(s.find(cnt[y]));
        s.erase(s.find(cnt[x]));
        cnt[x] += cnt[y];
        s.insert(cnt[x]);
        fa[y] = x;
    }
};

const int N = 1e5 + 5;
vector<int> opt[N];
int pre[N], suf[N];

void solve() {
    int n, k; cin >> n >> k;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        opt[a[i]].push_back(i);
        pre[i] = i - 1, suf[i] = i + 1;
    }
    
    auto dsu = new DSU(n + 1);
    string str; cin >> str; str = " " + str;
    
    for(int i = 1; i <= n; i++) {
        if(str[i] == '1') {
            dsu->cnt[i] = 1;
            dsu->s.insert(1);
        }
    }

    for(int i = 1; i < n; i++) if(str[i] == '1' && str[i + 1] == '1') dsu->merge(i, i + 1);
    
    int ans = 0, cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(str[i] == '1') ++cnt;
        else cnt = 0;
        ans = max(ans, cnt);
    }
    ans = (ans >= k);

    for(int i = 1; i <= 100000; i++) {
        for(auto p : opt[i]) {
            if(str[p] == '1') {
                int pp = dsu->find(p);
                dsu->s.erase(dsu->s.find(dsu->cnt[pp]));
                dsu->cnt[pp]--;
                if(dsu->cnt[pp]) dsu->s.insert(dsu->cnt[pp]);
            }

            int fr = pre[p], ba = suf[p];
            suf[pre[p]] = ba;
            pre[suf[p]] = fr;
            if(fr >= 1 && ba <= n && str[fr] == '1' && str[ba] == '1') {
                dsu->merge(fr, ba);
            }
            if(dsu->s.size() && *(--dsu->s.end()) >= k) {
                ans = i + 1;
            }
        }
    }
    cout << ans << "\n";
}

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

/*

5 2
1 2 3 4 5
01101

5 2
3 4 5 2 1
10101


*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7068kb

input:

5 2
1 2 3 4 5
01101

output:

2

result:

ok answer is '2'

Test #2:

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

input:

5 2
3 4 5 2 1
10101

output:

0

result:

ok answer is '0'

Test #3:

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

input:

1 1
1
1

output:

1

result:

ok answer is '1'

Test #4:

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

input:

1 1
1
0

output:

0

result:

ok answer is '0'

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 5908kb

input:

5 3
8 3 5 2 7
10101

output:

4

result:

wrong answer expected '5', found '4'