QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#622960 | #8783. Cherry Picking | Sword1E1 | WA | 2ms | 11916kb | C++20 | 1.8kb | 2024-10-09 08:59:02 | 2024-10-09 08:59:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define dbg(x...) \
do { \
std::cout << #x << " -> "; \
err(x); \
} while (0)
void err() {
std::cout << std::endl;
}
template<class T, class... Ts>
void err(T arg, Ts &... args) {
std::cout << fixed << setprecision(10) << arg << ' ';
err(args...);
}
const int maxn = 1e5 + 5;
int a[maxn];
string res;
vector<int>p[maxn];
struct SegTree {
#define ls(p) p << 1
#define rs(p) p << 1 | 1
int L[maxn << 2],R[maxn << 2],V[maxn << 2],Siz[maxn << 2];
inline void Push_up(int i) {
if (L[ls(i)] == Siz[ls(i)]) L[i] = L[ls(i)] + L[rs(i)];
else L[i] = L[ls(i)];
if (R[rs(i)] == Siz[rs(i)]) R[i] = R[rs(i)] + R[ls(i)];
else R[i] = R[rs(i)];
Siz[i] = Siz[ls(i)] + Siz[rs(i)];
V[i] = max({L[i],R[i],R[ls(i)] + L[rs(i)]});
}
void Build (int p,int l,int r) {
if (l == r) {
//dbg(l,Id[l]);
Siz[p] = 1;
V[p] = L[p] = R[p] = res[l - 1] - '0';
return;
}
int mid = (l + r) >> 1;
Build(ls(p),l,mid);
Build(rs(p),mid + 1,r);
Push_up(p);
}
void Update(int p,int l,int r,int x) {
if (l == r) {
L[p] = R[p] = Siz[p] = V[p] = 0;
return;
}
int mid = (l + r) >> 1;
if (x <= mid) Update(ls(p),l,mid,x);
else Update(rs(p),mid + 1,r,x);
Push_up(p);
}
} Tr;
void GENSHEN_START() {
int n,k;cin >> n >> k;
for (int i = 1;i <= n;i++) {
cin >> a[i];
p[a[i]].push_back(i);
}
cin >> res;
Tr.Build(1,1,n);
int ans = 0;
if (Tr.V[1] >= k) ans = 1;
for (int i = 1;i <= 1e5;i++) {
for (auto j : p[i]) {
Tr.Update(1,1,n,j);
}
if (Tr.V[1] >= k) ans = i + 1;
}
cout << ans << '\n';
return ;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);
int T = 1;
//cin >> T;
while (T--) GENSHEN_START();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11916kb
input:
5 2 1 2 3 4 5 01101
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 2ms
memory: 11864kb
input:
5 2 3 4 5 2 1 10101
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 9796kb
input:
1 1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 2ms
memory: 9808kb
input:
1 1 1 0
output:
0
result:
ok answer is '0'
Test #5:
score: 0
Accepted
time: 2ms
memory: 9868kb
input:
5 3 8 3 5 2 7 10101
output:
5
result:
ok answer is '5'
Test #6:
score: 0
Accepted
time: 2ms
memory: 11784kb
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: 2ms
memory: 9872kb
input:
10 1 6 7 2 10 8 4 4 9 7 9 0111011000
output:
10
result:
ok answer is '10'
Test #8:
score: 0
Accepted
time: 0ms
memory: 9804kb
input:
10 2 4 5 9 6 9 10 6 9 2 7 1100010100
output:
9
result:
ok answer is '9'
Test #9:
score: 0
Accepted
time: 0ms
memory: 11788kb
input:
10 3 2 10 8 5 8 3 7 9 9 1 1100011100
output:
3
result:
ok answer is '3'
Test #10:
score: 0
Accepted
time: 0ms
memory: 11844kb
input:
10 5 5 5 9 2 7 2 4 8 4 8 1010001100
output:
0
result:
ok answer is '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 11792kb
input:
10 10 6 5 8 3 2 8 6 4 5 5 0111001100
output:
0
result:
ok answer is '0'
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 11868kb
input:
100 1 13 90 87 79 34 66 76 58 65 37 63 38 84 88 89 98 63 55 16 39 64 50 28 64 4 69 40 51 75 37 11 9 20 29 36 29 30 61 38 54 92 78 72 36 78 24 78 8 98 11 2 41 64 51 45 67 27 80 67 84 73 50 99 82 39 70 84 18 54 43 85 96 59 98 82 5 57 46 68 31 97 89 21 65 57 37 58 25 30 40 15 76 44 85 75 65 22 97 93 82...
output:
90
result:
wrong answer expected '97', found '90'