QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#556835 | #8783. Cherry Picking | HTensor | WA | 2ms | 7068kb | C++17 | 2.5kb | 2024-09-10 21:19:52 | 2024-09-10 21:19:52 |
Judging History
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'