#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;
}
private:
ll sum = 0;
};
int bestcut[nmax];
ll dp[nmax];
ll spart[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) {
for(int i = 1; i <= n; i++) spart[i] += spart[i - 1]; 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]);
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 >> spart[i];
}
for(int i = 1; i <= n; i++)
cin >> v[i];
auto T = solve(n, 1);
reverse(spart + 1, spart + n + 1);
reverse(v + 1, v + n + 1);
auto T1 = solve(n, 0);
reverse(1 + all(T1));
for(int i = 1; i <= n; i++) cout << (T[i] || T1[i]);
cout << '\n';
}
Compilation message
trade.cpp: In function 'void Divide::divide(ll, ll)':
trade.cpp:82:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | int mid = l + r >> 1;
| ~~^~~
trade.cpp:93:17: warning: unused variable 'SA' [-Wunused-variable]
93 | int SA = S(mid, atr), SB = 0;
| ^~
trade.cpp: In function 'std::vector<long long int> solve(ll, bool)':
trade.cpp:128:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
128 | for(int i = 1; i <= n; i++) spart[i] += spart[i - 1]; bestcut[0] = 0;
| ^~~
trade.cpp:128:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
128 | for(int i = 1; i <= n; i++) spart[i] += spart[i - 1]; bestcut[0] = 0;
| ^~~~~~~
trade.cpp:143:8: warning: unused variable 'criteriaIL' [-Wunused-variable]
143 | int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
| ^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
