QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#545697 | #8783. Cherry Picking | lonelywolf | WA | 0ms | 3632kb | C++20 | 4.0kb | 2024-09-03 16:19:46 | 2024-09-03 16:19:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class Info>
struct SegmentTree {
int n;
vector<Info> info;
SegmentTree() : n(0) {}
SegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
SegmentTree(vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(vector(n_ + 1, v_));
}
template<class T>
void init(vector<T> init_) {
n = init_.size() - 1;
info.assign(4 << __lg(n) + 1, Info());
function<void(int, int, int)> build = [&](int p, int l, int r) {
if (l == r) {
info[p] = {init_[l]};
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pull(p);
};
build(1, 1, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {
if (l == r) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x <= m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m + 1, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 1, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l > y || r < x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m + 1, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 1, n, l, r);
}
// 线段树二分
template<class F>
int findFirst(int p, int l, int r, int x, int y, F pred) {
if (l > y || r < x || !pred(info[p])) {
return -1;
}
if (l == r) {
return l;
}
int m = (l + r) / 2;
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m + 1, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F pred) {
return findFirst(1, 1, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F pred) {
if (l > y || r < x || !pred(info[p])) {
return -1;
}
if (l == r) {
return l;
}
int m = (l + r) / 2;
int res = findLast(2 * p + 1, m + 1, r, x, y, pred);
if (res == -1) {
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F pred) {
return findLast(1, 1, n, l, r, pred);
}
};
struct Info {
int l = 0;
int r = 0;
int mx = 0;
int lmx = 0;
int rmx = 0;
};
Info operator+(Info a, Info b) {
Info ret;
ret.l = a.l, ret.r = b.r;
ret.mx = max({a.mx, b.mx, a.rmx + b.lmx});
ret.lmx = a.lmx;
if (a.lmx == a.r - a.l + 1) {
ret.lmx = a.lmx + b.lmx;
}
ret.rmx = b.rmx;
if (b.rmx == b.r - b.l + 1) {
ret.rmx = a.rmx + b.rmx;
}
return ret;
}
constexpr int inf = 1e9;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
string r;
map<int, vector<int>> mp;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mp[-a[i]].push_back(i);
}
cin >> r;
r = " " + r;
SegmentTree<Info> tr(n);
for (auto &[x, v] : mp) {
for (auto idx : v) {
if (r[idx] == '1') {
tr.modify(idx, {idx, idx, 1, 1, 1});
} else {
tr.modify(idx, {idx, idx, -inf, -inf, -inf});
}
}
auto t = tr.rangeQuery(1, n);
if (t.mx >= k) {
cout << -x << "\n";
return 0;
}
}
cout << 0 << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
input:
5 2 1 2 3 4 5 01101
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
5 2 3 4 5 2 1 10101
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
1 1 1 0
output:
0
result:
ok answer is '0'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3548kb
input:
5 3 8 3 5 2 7 10101
output:
0
result:
wrong answer expected '5', found '0'