| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 727891 | He_Huanglu | 휴가 (IOI14_holiday) | 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 int long long
using namespace std;
const int N = 1e5 + 5, maxn = 100;
int n, st, d, a[N];
long long res;
struct node {
int sum;
long long val;
node *left, *right;
node () {
sum = 0, val = 0;
left = right = nullptr;
}
};
node *t[N];
int sum(node *p) {
return p ? p->sum : 0;
}
long long val(node *p) {
return p ? p->val : 0;
}
void upd(node *x, int l, int r, int pos) {
if(l == r) {
x->sum += 1;
x->val += pos;
return ;
}
int mid = l + r >> 1;
if(pos <= mid) {
x->left = x->left ? new node(*x->left) : new node();
upd(x->left, l, mid, pos);
}
else {
x->right = x->right ? new node(*x->right) : new node();
upd(x->right, mid + 1, r, pos);
}
x->sum = sum(x->left) + sum(x->right);
x->val = val(x->left) + val(x->right);
}
long long get(node *xl, node *xr, int l, int r, int k) {
if(l == r) return l * min(k, sum(xr) - sum(xl));
int mid = l + r >> 1;
int cnt = sum(xr->right) - sum(xl->right);
if(cnt > k) {
xl->right = xl->right ? new node(*xl->right) : new node();
xr->right = xr->right ? new node(*xr->right) : new node();
return get(xl->right, xr->right, mid + 1, r, k);
}
else {
xl->left = xl->left ? new node(*xl->left) : new node();
xr->left = xr->left ? new node(*xr->left) : new node();
return val(xr->right) - val(xl->right) + get(xl->left, xr->left, l, mid, k - cnt);
}
}
long long cost(int l, int r) {
int k = d - (r - l + min(st - l, r - st));
if(k <= 0) return 0;
return get(t[l - 1], t[r], 0, maxn, min(k, r - l + 1));
}
void solve(int l, int r, int optl, int optr) {
if(l > r) return ;
int mid = l + r >> 1;
pair <long long, int> best = {-1, 0};
for(int i = optl; i <= min(mid, optr); i++) {
best = max(best, {cost(i, mid), i});
}
res = max(res, best.first);
solve(l, mid - 1, optl, best.second);
solve(mid + 1, r, best.second, optr);
}
long long findMaxAttraction(int N, int Start, int D, int a[]) {
t[0] = new node();
n = N, d = D, st = Start + 1;
for(int i = 1; i <= n; i++) {
t[i] = new node(*t[i - 1]);
upd(t[i], 0, maxn, a[i - 1]);
}
solve(st, n, 1, st);
return res;
}
//main () {
// cin.tie(0)->sync_with_stdio(0);
// if(fopen("task.inp", "r")) {
// freopen("task.inp", "r", stdin);
// freopen("wa.out", "w", stdout);
// }
// cin >> n >> st >> d;
// for(int i = 0; i < n; i++) cin >> a[i];
// cout << findMaxAttraction(n, st, d, a);
//}