| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 849603 | skittles1412 | Closing Time (IOI23_closing) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/extc++.h"
using namespace std;
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t;
((cerr << " | " << u), ...);
cerr << endl;
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...)
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
struct MArr {
vector<long> vals;
vector<int> comp;
MArr(const vector<long>& vals) : vals(vals), comp(sz(vals)) {
vector<pair<long, int>> v;
for (int i = 0; i < sz(vals); i++) {
v.emplace_back(vals[i], i);
}
sort(begin(v), end(v));
for (int i = 0; i < sz(v); i++) {
comp[v[i].second] = i;
}
}
};
struct Node {
long sum, last0, last1;
int cnt;
Node operator+(const Node& n) const {
if (n.last1 == -1) {
return {sum + n.sum, last0, last1, cnt + n.cnt};
} else if (n.last0 == -1) {
return {sum + n.sum, last1, n.last1, cnt + n.cnt};
} else {
return {sum + n.sum, n.last0, n.last1, cnt + n.cnt};
}
}
static Node c_from(long x) {
return {x, -1, x, 1};
}
static Node c_def() {
return {0, -1, -1, 0};
}
};
struct ST {
int n;
vector<Node> v;
ST(int n) : n(n), v(4 * n, Node::c_def()) {}
void update(int o, int l, int r, int ind, const Node& x) {
if (l == r) {
v[o] = x;
return;
}
int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
if (ind <= mid) {
update(lc, l, mid, ind, x);
} else {
update(rc, mid + 1, r, ind, x);
}
v[o] = v[lc] + v[rc];
}
void update(int ind, const Node& x) {
update(1, 0, n - 1, ind, x);
}
Node query(int o, int l, int r, int ql, int qr) const {
if (ql <= l && r <= qr) {
return v[o];
}
int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
if (ql <= mid) {
if (mid < qr) {
return query(lc, l, mid, ql, qr) +
query(rc, mid + 1, r, ql, qr);
}
return query(lc, l, mid, ql, qr);
}
return query(rc, mid + 1, r, ql, qr);
}
Node query(int l, int r) const {
if (l > r) {
return Node::c_def();
}
return query(1, 0, n - 1, l, r);
}
Node query_all() const {
return v[1];
}
template <typename Cb>
pair<int, Node> bsearch(int o, int l, int r, const Node& pref, const Cb& cb)
const {
if (l == r) {
return {l - 1, pref};
}
int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
if (!cb(pref + v[lc])) {
return bsearch(lc, l, mid, pref, cb);
} else {
return bsearch(rc, mid + 1, r, pref + v[lc], cb);
}
}
template <typename Cb>
pair<int, Node> bsearch(const Cb& cb) const {
if (cb(v[1])) {
return {n, v[1]};
}
return bsearch(1, 0, n - 1, Node::c_def(), cb);
}
};
struct DS {
MArr arr[2];
ST v_st[2];
set<int> v_inds[2];
DS(const vector<long>& v0, const vector<long>& v1)
: arr {v0, v1}, v_st {sz(v0), sz(v1)} {}
void insert(int ind, int x) {
dbg("+", ind, arr[ind].vals[x]);
v_inds[ind].insert(arr[ind].comp[x]);
v_st[ind].update(arr[ind].comp[x], Node::c_from(arr[ind].vals[x]));
}
void erase(int ind, int x) {
dbg("-", ind, arr[ind].vals[x]);
v_inds[ind].insert(arr[ind].comp[x]);
v_st[ind].update(arr[ind].comp[x], Node::c_def());
}
int query(long kv) {
int ans = -1e9;
auto upd_ans = [&](int ind) -> void {
ind = clamp(ind, -1, v_st[0].n);
auto q0 = v_st[0].query(0, ind),
q1 = v_st[1]
.bsearch([&](const Node& o) -> bool {
return q0.sum + o.sum <= kv;
})
.second;
if (q0.sum + q1.sum <= kv) {
ans = max(ans, q0.cnt * 2 + q1.cnt);
}
};
int l = -1, r = v_st[0].n;
while (r - l > 1) {
int mid = (l + r) / 2;
auto q0 = v_st[0].query(0, mid),
q1 = v_st[1]
.bsearch([&](const Node& o) -> bool {
return q0.sum + o.sum <= kv;
})
.second;
if (q0.sum + q1.sum <= kv &&
((q1.last0 == -1 && q1.last1 * 2 > q0.last1) ||
(q1.last0 != -1 && q1.last0 + q1.last1 > q0.last1))) {
l = mid;
} else {
r = mid;
}
}
auto upd_ans2 = [&](int ind) -> void {
upd_ans(ind - 1);
upd_ans(ind);
upd_ans(ind + 1);
};
upd_ans2(l);
upd_ans2(0);
upd_ans2(
v_st[0]
.bsearch([&](const Node& o) -> bool { return o.sum <= kv; })
.first);
upd_ans2(v_st[0]
.bsearch([&](const Node& o) -> bool {
return o.sum <= kv - v_st[1].query_all().sum;
})
.first);
auto upd_rep = [&](auto cb) -> void {
int u = l;
for (int it = 0; it < 2; it++) {
auto n_u = cb(u);
if (!n_u) {
return;
}
u = n_u.value();
upd_ans2(u);
}
};
upd_rep([&](int u) -> optional<int> {
auto it = v_inds[0].lower_bound(u);
if (it == v_inds[0].begin()) {
return {};
}
return *(--it);
});
upd_rep([&](int u) -> optional<int> {
auto it = v_inds[0].upper_bound(u);
if (it == v_inds[0].end()) {
return {};
}
return *it;
});
return ans;
}
};
void solve() {
int n, q;
cin >> n >> q;
vector<long> v0(n), v1(n);
for (auto& a : v0) {
cin >> a;
}
for (auto& a : v1) {
cin >> a;
}
DS ds(v0, v1);
for (int i = 0; i < n; i++) {
int ty;
cin >> ty;
ds.insert(ty, i);
}
while (q--) {
long kv;
cin >> kv;
cout << ds.query(kv) << endl;
}
}
int main() {
cin.tie(nullptr);
cin.exceptions(ios::failbit);
ios_base::sync_with_stdio(false);
solve();
}