| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1092931 | shivansh0809 | Holiday (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 "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct PersistentSegTree
{ // find_kth returns the kth smallest element in the array in [l, r)
struct Vertex
{
Vertex *l, *r;
int sum;
int k_sum;
Vertex(int val) : l(nullptr), r(nullptr), sum(val), k_sum(0) {}
Vertex(int val, int k_sum) : l(nullptr), r(nullptr), sum(val), k_sum(k_sum) {}
Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0), k_sum(0)
{
if (l)
sum += l->sum, k_sum += l->k_sum;
if (r)
sum += r->sum, k_sum += r->k_sum;
}
};
vector<Vertex *> roots;
map<int, pair<int, int>> compress;
int n;
PersistentSegTree(vector<int> v) : n(v.size())
{
int tl = 0, tr = n;
vector<pair<int, int>> sort_v;
for (int i = 0; i < n; i++)
sort_v.push_back({v[i], i});
sort(sort_v.begin(), sort_v.end(), greater<pair<int, int>>());
vector<int> idx(n);
for (int i = 0; i < n; i++)
compress[i] = sort_v[i], idx[sort_v[i].second] = i;
roots.push_back(build(tl, tr));
for (int i = 0; i < n; i++)
roots.push_back(update(roots.back(), tl, tr, idx[i]));
}
Vertex *build(int tl, int tr)
{
if (tl == tr)
return new Vertex(0LL, 0LL);
int tm = (tl + tr) / 2;
return new Vertex(build(tl, tm), build(tm + 1, tr));
}
Vertex *update(Vertex *v, int tl, int tr, int pos)
{
if (tl == tr)
return new Vertex(v->sum + 1, v->k_sum + compress[pos].first);
int tm = (tl + tr) / 2;
if (pos <= tm)
return new Vertex(update(v->l, tl, tm, pos), v->r);
else
return new Vertex(v->l, update(v->r, tm + 1, tr, pos));
}
int find_kth(Vertex *vl, Vertex *vr, int tl, int tr, int k)
{
if (tl == tr)
return vr->k_sum - vl->k_sum;
int tm = (tl + tr) / 2;
int left_count = vr->l->sum - vl->l->sum;
if (left_count >= k)
return find_kth(vl->l, vr->l, tl, tm, k);
return vr->l->k_sum - vl->l->k_sum + find_kth(vl->r, vr->r, tm + 1, tr, k - left_count);
}
int find_kth(int l, int r, int k)
{
return find_kth(roots[l], roots[r], 0, n, k);
}
};
long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
int ans = 0;
PersistentSegTree pst(vector<int>(attraction, attraction + n));
function<int(int, int)> C1 = [&](int k, int mid) -> int
{
int days_rem = d - (mid - k + max(0LL, start - k));
if (days_rem <= 0)
return 0;
return pst.find_kth(k, mid + 1, days_rem);
// return mid - k;
};
function<int(int, int)> C2 = [&](int mid, int k) -> int
{
int days_rem = d - (k - mid + max(0LL, k - start));
if (days_rem <= 0)
return 0;
return pst.find_kth(mid, k + 1, days_rem);
// return k - mid;
};
function<void(int, int, int, int)> dncg = [&](int l, int r, int optl, int optr)
{
if (l > r)
return;
int mid = (l + r) >> 1;
pair<long long, int> best = {-1, -1};
for (int k = optl; k <= min(mid, optr); k++)
best = max(best, {C1(k, mid), k});
// debug(dp, best, ndp);
// debug(ans, best, mid);
ans = max(best.first, ans);
int opt = best.second;
dncg(l, mid - 1, optl, opt);
dncg(mid + 1, r, opt, optr);
};
function<void(int, int, int, int)> dncs = [&](int l, int r, int optl, int optr)
{
if (l > r)
return;
int mid = (l + r) >> 1;
pair<long long, int> best = {-1, -1};
for (int k = optr; k >= max(mid, optl); k--)
best = max(best, {C2(mid, k), k});
// debug(dp, best, ndp);
// debug(ans, best, mid);
ans = max(best.first, ans);
int opt = best.second;
dncs(l, mid - 1, optl, opt);
dncs(mid + 1, r, opt, optr);
};
dncg(start, n - 1, 0, n - 1);
dncs(0, start - 1, 0, n - 1);
return ans;
}