| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 852356 | adaawf | Holiday (IOI14_holiday) | C++14 | 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 <iostream>
#include <vector>
#include <algorithm>
#include "holiday.h"
using namespace std;
pair<int, int> a[100005];
long long f[100005], g[100005], res = 0;
int d;
struct DAY {
long long int res, c;
};
DAY t[400005];
void update(int v, int x) {
v += 100005;
if (res < 0) t[v].c = 0;
else t[v].c = 1;
t[v].res += x;
v /= 2;
while (v > 0) {
t[v].c = t[v * 2].c + t[v * 2 + 1].c;
t[v].res = t[v * 2].res + t[v * 2 + 1].res;
v /= 2;
}
}
long long int sum(int v, int l, int r, int x) {
if (t[v].c == 0 || x <= 0) return 0;
if (t[v].c <= x) return t[v].res;
int mid = (l + r) / 2;
if (t[v * 2 + 1].c >= x) return sum(v * 2 + 1, mid + 1, r, x);
return t[v * 2 + 1].res + sum(v * 2, l, mid, x - t[v * 2 + 1].c);
}
int ll = 0, rr = -1;
void trya(int x, int y) {
while (ll > x) {
ll--;
update(a[ll].second, a[ll].first);
}
while (rr < y) {
rr++;
update(a[rr].second, a[rr].first);
}
while (ll < x) {
update(a[ll].second, -a[ll].first);
ll++;
}
while (rr > y) {
update(a[rr].second, -a[rr].first);
rr--;
}
}
void dnc(int l, int r, int x, int y, int k) {
if (l > r) return;
int mid = (l + r) / 2;
trya(x, mid);
int h = x;
for (int i = x; i <= min(mid, y) && i <= k; i++) {
int c = (k - i) + (mid - i);
if (d - c > 0) {
long long int k = sum(1, 0, 100004, d - c);
if (f[mid] <= k) {
f[mid] = k;
res = max(res, k);
h = i;
}
}
update(a[i].second, -a[i].first);
ll++;
}
dnc(l, mid - 1, x, h, k);
dnc(mid + 1, r, h, y, k);
}
void dnc2(int l, int r, int x, int y, int k) {
if (l > r) return;
int mid = (l + r) / 2;
trya(mid, y);
int h = y;
for (int i = y; i >= max(mid, x) && i >= k; i--) {
int c = (i - k) + (i - mid);
if (d - c > 0) {
long long k = sum(1, 0, 100004, d - c);
if (g[mid] <= k) {
g[mid] = k;
res = max(res, k);
h = i;
}
}
update(a[i].second, -a[i].first);
rr--;
}
dnc2(l, mid - 1, x, h, k);
dnc2(mid + 1, r, h, y, k);
}
long long int findMaxAttraction(int n, int k, int dd, int attraction[]) {
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) {
v.push_back({attraction[i], i});
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
a[v[i].second] = {v[i].first, id};
}
d = dd;
dnc(k, n - 1, 0, n - 1, k);
dnc2(0, k, 0, n - 1, k);
return res;
}