| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1077541 | bleahbleah | Tricks of the Trade (CEOI23_trade) | 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/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 25e4 + 5;
int K;
const ll inf = 1e18;
struct KthHeap {
multiset<int> outside, inside;
void repair() {
while(sz(inside) > K) {
int x = *inside.begin();
inside.erase(inside.find(x));
outside.insert(x);
sum -= x;
}
while(sz(inside) < K && sz(outside)) {
int x = *outside.rbegin();
outside.erase(outside.find(x));
inside.insert(x);
sum += x;
}
while(sz(inside) && sz(outside) && *inside.begin() < *outside.rbegin()) {
int x = *outside.rbegin(), y = *inside.begin();
outside.erase(outside.find(x));
inside.erase(inside.find(y));
outside.emplace(y);
inside.emplace(x);
sum += x - y;
}
return;
}
void erase(int x) {
if(outside.find(x) != outside.end())
outside.erase(outside.find(x));
else if(inside.find(x) != inside.end())
inside.erase(inside.find(x)), sum -= x;
else assert(false);
repair();
}
void insert(int x) {
outside.emplace(x);
repair();
}
ll query() {
repair();
if(sz(inside) < K) return -inf;
return sum;
}
void clear() { inside.clear(); outside.clear(); }
private:
ll sum = 0;
};
int bestcut[nmax];
ll dp[nmax];
ll spart[nmax];
ll S[nmax];
ll v[nmax];
ll V[nmax];
ll S(int l, int r) { return spart[r] - spart[l - 1]; }
namespace Divide {
KthHeap hint;
void divide(int l, int r) {
if(l + 1 == r) return;
int optl = bestcut[l], optr = bestcut[r];
int mid = l + r >> 1;
if(r <= optl) {
for(int i = mid; i < r; i++) hint.insert(v[i]);
ll best = hint.query() - S(mid, optl);
int atr = optl;
for(int i = optl + 1; i <= optr; i++) {
hint.insert(v[i]);
if(hint.query() - S(mid, i) >= best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i);
}
bestcut[mid] = atr, dp[mid] = best;
if(atr - mid + 1 == K) {
int SA = S(mid, atr), SB = 0;
for(int i = mid; i <= atr; i++) SB += v[i];
}
for(int i = optl + 1; i <= optr; i++) hint.erase(v[i]);
divide(l, mid);
for(int i = mid; i < r; i++) hint.erase(v[i]);
for(int i = optl + 1; i <= atr; i++) hint.insert(v[i]);
divide(mid, r);
for(int i = optl + 1; i <= atr; i++) hint.erase(v[i]);
}
else {
int border = max(mid - 1, optl);
for(int i = mid; i <= border; i++) hint.insert(v[i]);
ll best = hint.query() - S(mid, border), atr = border;
for(int i = border + 1; i <= optr; i++) {
hint.insert(v[i]);
if(hint.query() - S(mid, i) >= best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i);
}
bestcut[mid] = atr, dp[mid] = best;
for(int i = optr; i > border; i--) hint.erase(v[i]);
divide(l, mid);
for(int i = mid; i <= border; i++) hint.erase(v[i]);
for(int i = r; i <= atr; i++) hint.insert(v[i]);
divide(mid, r);
for(int i = r; i <= atr; i++) hint.erase(v[i]);
}
}
}
vector<int> solve(int n, bool first = 1) {
Divide::hint.clear();
for(int i = 1; i <= n; i++) spart[i] = S[i] + spart[i - 1], dp[i] = -inf, bestcut[i] = 0;
bestcut[0] = 0;
bestcut[n - K + 2] = n;
Divide::divide(0, n - K + 2);
ll mx = -inf;
vector<int> possible(n + 1);
for(int i = 1; i <= n - K + 1; i++)
mx = max(mx, dp[i]);
if(first)
cout << mx << '\n';
auto cmp = [&](int a, int b) { return (v[a] < v[b] || (v[a] == v[b] && a < b)); };
set<int, decltype(cmp)> inside(cmp), outside(cmp);
int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
KthHeap forchristsake;
for(int i = 1; i <= n; i++) {
//cerr << i << ' ' << bestcut[i] << ' ' << forchristsake.query() << '\t';
//for(auto x : forchristsake.inside) cerr << x << ' ';
//for(auto x : forchristsake.outside) cerr << x << ' ';
//cerr << '\n';
for(int j = bestcut[i - 1] + 1; j <= bestcut[i]; j++) {
forchristsake.insert(v[j]);
inside.insert(j);
while(sz(inside) > K && [&]() {
auto it = inside.begin(), it2 = next(it);
return v[*it] < v[*it2];
}()) {
auto t = *inside.begin();
if(t <= criteriaIR && v[t] >= criteriaV) possible[t] = 1;
inside.erase(inside.begin());
outside.insert(t);
}
//cerr << '\t' << i << ' ' << j << ' ' << forchristsake.query() << ' ' << S(i, j) << '\n';
if(forchristsake.query() - S(i, j) == mx) {
criteriaIR = bestcut[i];
criteriaV = v[*inside.begin()];
}
}
if(dp[i] == mx) {
criteriaIR = bestcut[i];
criteriaV = v[*inside.begin()];
//for(auto x : inside) cerr << x << ' ';
//cerr << '\n';
//cerr << criteriaIR << ' ' << criteriaV << '\n';
}
forchristsake.erase(v[i]);
if(inside.count(i)) {
if(criteriaIR >= i && v[i] >= criteriaV) possible[i] = 1;
inside.erase(i);
}
else if(outside.count(i)) outside.erase(i);
while(sz(inside) < K && sz(outside)) {
int a = *outside.rbegin();
outside.erase(a);
inside.insert(a);
}
}
while(!inside.empty()) {
int t = *inside.begin();
//cerr << t << ' ' << (t <= criteriaIR && v[t] >= criteriaV) << '\n';
if(t <= criteriaIR && v[t] >= criteriaV) possible[t] = 1;
inside.erase(inside.begin());
}
for(int i = n; i > 0; i--) spart[i] -= spart[i - 1];
return possible;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n;
cin >> n >> K;
for(int i = 1; i <= n; i++) {
cin >> S[i];
}
for(int i = 1; i <= n; i++)
cin >> v[i], V[i] = v[i];
auto T = solve(n, 1);
reverse(S + 1, S + n + 1);
reverse(V + 1, V + n + 1);
for(int i = 1; i <= n; i++) v[i] = V[i];
auto T1 = solve(n, 0);
for(int i = 1; i <= n; i++) cout << (T[i] || T1[n - i + 1]);
cout << '\n';
}