| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 170726 | DS007 | 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 <bits/stdc++.h>
// #include <holiday.h>
using namespace std;
struct node {
long long val;
int size;
int left, right;
node() {
val = size = 0;
left = right = 0;
}
} nodes[2200000];
const int NN = 1e5, DD = 2 * NN + NN / 2;
map<long long, long long> m1, m2;
int v[NN + 1];
int con = 0;
int N, START, D, *ATTRACTION;
long long dp1[DD + 1], dp2[DD + 1], dp3[DD + 1], dp4[DD + 1];
// int l1[DD + 1], l2[DD + 1], l3[DD + 1], l4[DD + 1];
void pre() {
int copy[N];
for (int i = 0; i < N; i++)
copy[i] = ATTRACTION[i];
sort(copy, copy + N);
set<int> s;
for (int i = 0, j = 0; i < N; i++) {
if (s.count(copy[i]))
continue;
m1[copy[i]] = j;
m2[j++] = copy[i];
}
}
void update(int cur, int prev, int tl, int tr, int l) {
if (l == tl && tl == tr) {
nodes[cur].val = nodes[prev].val + m2[l];
nodes[cur].size = nodes[prev].size + 1;
return;
}
int tm = (tl + tr) / 2;
if (l <= tm) {
nodes[cur].right = nodes[prev].right;
nodes[cur].left = con++;
update(nodes[cur].left, nodes[prev].left, tl, tm, l);
} else {
nodes[cur].left = nodes[prev].left;
nodes[cur].right = con++;
update(nodes[cur].right, nodes[prev].right, tm + 1, tr, l);
}
nodes[cur].val = nodes[nodes[cur].left].val + nodes[nodes[cur].right].val;
nodes[cur].size = nodes[nodes[cur].left].size + nodes[nodes[cur].right].size;
}
void build(int n, int tl, int tr) {
if (tl == tr)
return;
nodes[n].left = con++;
nodes[n].right = con++;
int tm = (tl + tr) / 2;
build(nodes[n].left, tl, tm);
build(nodes[n].right, tm + 1, tr);
}
void build() {
v[0] = con++;
build(v[0], 0, N - 1);
for (int i = 1; i <= N; i++) {
v[i] = con++;
update(v[i], v[i - 1], 0, N - 1, m1[ATTRACTION[i - 1]]);
}
}
long long query(int n1, int n2, int tl, int tr, int c) {
c = min(c, nodes[n2].size - nodes[n1].size);
if (c <= 0)
return 0;
if (nodes[n2].size - nodes[n1].size == c)
return nodes[n2].val - nodes[n1].val;
if (tl == tr)
return m2[tl] * c;
int tm = (tl + tr) / 2;
if (nodes[nodes[n2].right].size - nodes[nodes[n1].right].size >= c)
return query(nodes[n1].right, nodes[n2].right, tm + 1, tr, c);
else
return query(nodes[n1].right, nodes[n2].right, tm + 1, tr, nodes[nodes[n2].right].size - nodes[nodes[n1].right].size) + query(nodes[n1].left, nodes[n2].left, tl, tm, c - (nodes[nodes[n2].right].size - nodes[nodes[n1].right].size));
}
/*void calc1() {
dp1[1] = dp1[2] = ATTRACTION[START];
l1[1] = l1[2] = START;
for (int i = 3; i <= D; i++) {
int t = query(v[l1[i - 1]], v[START + 1], i - 2 * (START - l1[i - 1])), j = l1[i - 1] - 1;
while (j >= 0) {
int temp = query(v[j], v[START + 1], i - 2 * (START - j));
if (temp < t)
break;
t = temp;
j--;
}
dp1[i] = t;
l1[i] = j == -1 ? 0 : j;
}
}*/
void calc1() {
pair<long long, int> best = {ATTRACTION[START], START};
for (int i = START - 1; i >= 0; i--)
best = max(best, {query(v[i], v[START + 1], 0, N - 1, D - 2 * (START - i)), i});
dp1[D] = best.first;
// l1[D] = best.second;
int l = best.second;
for (int i = D - 1; i >= 0; i--) {
pair<long long, int> t = {query(v[l], v[START + 1], 0, N - 1, i - 2 * (START - l)), l};
for (int j = l + 1; j <= START; j++) {
pair<long long, int> temp = {query(v[j], v[START + 1], 0, N - 1, i - 2 * (START - j)), j};
if (max(t, temp) == t)
break;
t = temp;
}
dp1[i] = t.first;
l = t.second;
}
}
/*void calc2() {
dp2[1] = dp2[2] = ATTRACTION[START];
l2[1] = l2[2] = START;
for (int i = 3; i <= D; i++) {
int t = query(v[START], v[l2[i - 1] + 1], i - 2 * (l1[i - 1] - START)), j = l1[i - 1] + 1;
while (j < N) {
int temp = query(v[START], v[j + 1], i - 2 * (j - START));
if (temp < t)
break;
t = temp;
j++;
}
dp2[i] = t;
l2[i] = j == N ? N - 1 : j;
}
}*/
void calc2() {
pair<long long, int> best = {ATTRACTION[START], START};
for (int i = START + 1; i < N; i++)
best = max(best, {query(v[START], v[i + 1], 0, N - 1, D - 2 * (i - START)), i});
dp2[D] = best.first;
// l2[D] = best.second;
int l = best.second;
for (int i = D - 1; i >= 0; i--) {
pair<long long, int> t = {query(v[START], v[l + 1], 0, N - 1, i - 2 * (l - START)), l};
for (int j = l - 1; j >= START; j--) {
pair<long long, int> temp = {query(v[START], v[j + 1], 0, N - 1, i - 2 * (j - START)), j};
if (max(t, temp) == t)
break;
t = temp;
}
dp2[i] = t.first;
l = t.second;
}
}
/*void calc3() {
dp3[1] = ATTRACTION[START + 1];
l3[1] = START + 1;
for (int i = 2; i <= D; i++) {
int t = query(v[START + 1], v[l3[i - 1] + 1], i - (l3[i - 1] - START - 1)), j = l3[i - 1] + 1;
while (j < N) {
int temp = query(v[START + 1], v[j + 1], i - (j - START - 1));
if (temp < t)
break;
t = temp;
j++;
}
dp3[i] = t;
l3[i] = j == N ? N - 1 : j;
}
}*/
void calc3() {
pair<long long, int> best = {ATTRACTION[START + 1], START + 1};
for (int i = START + 2; i < N; i++)
best = max(best, {query(v[START + 1], v[i + 1], 0, N - 1, D - (i - START - 1)), i});
dp3[D] = best.first;
// l3[D] = best.second;
int l = best.second;
for (int i = D - 1; i >= 0; i--) {
pair<long long, int> t = {query(v[START + 1], v[l + 1], 0, N - 1, i - (l - START - 1)), l};
for (int j = l - 1; j >= START + 1; j--) {
pair<long long, int> temp = {query(v[START + 1], v[j + 1], 0, N - 1, i - (j - START - 1)), j};
if (max(t, temp) == t)
break;
t = temp;
}
dp3[i] = t.first;
l = t.second;
}
}
/*void calc4() {
dp4[1] = ATTRACTION[START - 1];
l4[1] = START - 1;
for (int i = 2; i <= D; i++) {
int t = query(v[l4[i - 1]], v[START], i - (START - 1 - l4[i - 1])), j = l4[i - 1] - 1;
while (j >= 0) {
int temp = query(v[j], v[START], i - (START - 1 - j));
if (temp < t)
break;
}
}
}*/
void calc4() {
pair<long long, int> best = {ATTRACTION[START - 1], START - 1};
for (int i = START - 2; i >= 0; i--)
best = max(best, {query(v[i], v[START], 0, N - 1, D - (START - 1 - i)), i});
dp4[D] = best.first;
// l4[D] = best.second;
int l = best.second;
for (int i = D - 1; i >= 0; i--) {
pair<long long, int> t = {query(v[l], v[START], 0, N - 1, i - (START - 1 - l)), l};
for (int j = l + 1; j <= START - 1; j++) {
pair<long long, int> temp = {query(v[j], v[START], 0, N - 1, i - (START - 1 - j)), j};
if (max(t, temp) == t)
break;
t = temp;
}
dp4[i] = t.first;
l = t.second;
}
}
long long answer() {
long long ans = max(dp1[D], dp2[D]);
for (int i = 0; i <= D - 1; i++) {
ans = max(ans, dp1[i] + dp3[D - i - 1]);
ans = max(ans, dp2[i] + dp4[D - i - 1]);
}
return ans;
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n;
START = start;
D = d;
ATTRACTION = attraction;
pre();
build();
calc1();
calc2();
if (START != N - 1)
calc3();
if (START)
calc4();
return answer();
}
int main() {
int n, start, d;
int attraction[100000];
int i, n_s;
n_s = scanf("%d %d %d", &n, &start, &d);
for (i = 0 ; i < n; ++i) {
n_s = scanf("%d", &attraction[i]);
}
cout << findMaxAttraction(n, start, d, attraction) << endl;
cout << con << endl;
return 0;
}