#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100100;
struct node
{
ll sum, act;
node(ll _sum = 0, ll _act = 0)
{
sum = _sum;
act = _act;
}
};
node merge_node(node lf, node rf)
{
node nd;
nd.sum = lf.sum + rf.sum;
nd.act = lf.act + rf.act;
return nd;
}
ll value[maxn], pos[maxn];
node tree[4 * maxn];
int n;
void toggle(int root, int left, int right, int pos, int type)
{
if (left == right)
{
if (type == 1)
{
tree[root].sum = value[left];
tree[root].act = 1;
}
else
{
tree[root].sum = 0;
tree[root].act = 0;
}
return;
}
int mid = (left + right) / 2;
if (pos <= mid)
toggle(root * 2, left, mid, pos, type);
else
toggle(root * 2 + 1, mid + 1, right, pos, type);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
///cout << "back " << root << " " << tree[root].sum << " " << pos << " " << type << endl;
}
ll get_sum(int root, int left, int right, int k)
{
if (tree[root].act == 0 || k == 0)
return 0;
if (tree[root].act <= k)
return tree[root].sum;
int mid = (left + right) / 2;
if (tree[root * 2 + 1].act >= k)
return get_sum(root * 2 + 1, mid + 1, right, k);
return get_sum(root * 2, left, mid, k - tree[root * 2 + 1].act) + tree[root * 2 + 1].sum;
}
int lf, rf;
void cost(int left, int right)
{
/**for (int i = 0; i < 4 * n; i ++)
tree[i] = node();
for (int i = left; i <= right; i ++)
toggle(1, 0, n - 1, pos[i], 1);
return;*/
while(rf < right)
{
rf ++;
toggle(1, 0, n - 1, pos[rf], 1);
///cout << "activate " << value[pos[rf]] << " " << pos[rf] << endl;
}
while(lf > left)
{
lf --;
toggle(1, 0, n - 1, pos[lf], 1);
}
while(rf > right)
{
toggle(1, 0, n - 1, pos[rf], 0);
rf --;
}
while(lf < left)
{
///cout << "deactivate " << value[pos[lf]] << " " << pos[lf] << endl;
toggle(1, 0, n - 1, pos[lf], 0);
lf ++;
}
}
int pivot, hol;
ll dp_after[maxn * 3], dp_before[maxn * 3];
void divide_after(int left, int right, int optl, int optr)
{
if (left > right)
return;
int mid = (left + right) / 2;
int opt = -1;
dp_after[mid] = -1;
for (int i = max(pivot, optl); i <= min(n - 1, optr); i ++)
{
cost(pivot, i);
ll cur = 0;
if (mid - (i - pivot) > 0)
cur = get_sum(1, 0, n - 1, mid - (i - pivot));
///cout << i << " :: " << cur << " " << mid - (i - pivot) << endl;
if (cur > dp_after[mid])
{
dp_after[mid] = cur;
opt = i;
}
}
if (opt == -1)
{
opt = optl;
dp_after[mid] = 0;
}
///cout << "divide_after " << mid << " " << opt << " " << dp_after[mid] << " " << optl << " " << optr << endl;
divide_after(left, mid - 1, optl, opt);
divide_after(mid + 1, right, opt, optr);
}
void divide_before(int left, int right, int optl, int optr)
{
if (left > right)
return;
int mid = (left + right) / 2;
int opt = -1;
dp_before[mid] = -1;
for (int i = max(0, optl); i <= min(pivot - 1, optr); i ++)
{
cost(i, pivot - 1);
ll cur = 0;
if (mid - (pivot - i) * 2 > 0)
cur = get_sum(1, 0, n - 1, mid - (pivot - i) * 2);
///cout << i << " : " << mid - (pivot - i) * 2 << " " << cur << endl;
if (cur >= dp_before[mid])
{
dp_before[mid] = cur;
opt = i;
}
}
if (opt == -1)
{
opt = optl;
dp_before[mid] = 0;
}
///cout << "divide before " << mid << " " << opt << " " << dp_before[mid] << " " << optl << " " << optr << endl;
divide_before(left, mid - 1, opt, optr);
divide_before(mid + 1, right, optl, opt);
}
ll action(int attraction[])
{
/**cout << "---------------" << endl;
for (int i = 0; i < n; i ++)
cout << attraction[i] << " ";
cout << endl;*/
vector < pair < int, int > > pr;
for (int i = 0; i < n; i ++)
{
pr.push_back({attraction[i], i});
}
sort(pr.begin(), pr.end());
for (int i = 0; i < n; i ++)
{
value[i] = pr[i].first;
pos[pr[i].second] = i;
}
for (int i = 0; i < 4 * n; i ++)
tree[i] = node();
lf = 0;
rf = -1;
divide_after(0, hol, pivot, n - 1);
for (int i = 0; i < 4 * n; i ++)
tree[i] = node();
lf = 0;
rf = -1;
divide_before(0, hol, 0, pivot - 1);
for (int i = 1; i <= hol; i ++)
{
dp_after[i] = max(dp_after[i], dp_after[i - 1]);
dp_before[i] = max(dp_before[i], dp_before[i - 1]);
}
/**for (int i = 0; i <= hol; i ++)
cout << dp_after[i] << " ";
cout << endl;*/
ll ans = 0;
for (int i = 0; i <= hol; i ++)
{
///cout << dp_before[i] << " " << dp_after[hol - i] << " " << i << " " << hol - i << endl;
ans = max(ans, dp_before[i] + dp_after[hol - i]);
///cout << ans << endl;
}
///cout << ans << endl;
return ans;
}
long long int findMaxAttraction(int N, int start, int d, int attraction[])
{
pivot = start;
hol = d;
n = N;
ll ans = action(attraction);
start = N - start - 1;
pivot = start;
reverse(attraction, attraction + N);
ans = max(ans, action(attraction));
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6868 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6868 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6964 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6868 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6876 KB |
Output is correct |
| 7 |
Correct |
3 ms |
6868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
794 ms |
13456 KB |
Output is correct |
| 2 |
Correct |
731 ms |
13460 KB |
Output is correct |
| 3 |
Correct |
828 ms |
13520 KB |
Output is correct |
| 4 |
Correct |
741 ms |
13456 KB |
Output is correct |
| 5 |
Correct |
1068 ms |
12280 KB |
Output is correct |
| 6 |
Correct |
298 ms |
10652 KB |
Output is correct |
| 7 |
Correct |
518 ms |
10056 KB |
Output is correct |
| 8 |
Correct |
627 ms |
10268 KB |
Output is correct |
| 9 |
Correct |
209 ms |
11304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
7128 KB |
Output is correct |
| 2 |
Correct |
16 ms |
7132 KB |
Output is correct |
| 3 |
Correct |
16 ms |
7192 KB |
Output is correct |
| 4 |
Correct |
18 ms |
7124 KB |
Output is correct |
| 5 |
Correct |
17 ms |
7124 KB |
Output is correct |
| 6 |
Correct |
7 ms |
7020 KB |
Output is correct |
| 7 |
Correct |
6 ms |
6996 KB |
Output is correct |
| 8 |
Correct |
6 ms |
6996 KB |
Output is correct |
| 9 |
Correct |
6 ms |
6996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
805 ms |
14160 KB |
Output is correct |
| 2 |
Correct |
945 ms |
14244 KB |
Output is correct |
| 3 |
Correct |
362 ms |
8692 KB |
Output is correct |
| 4 |
Correct |
16 ms |
7096 KB |
Output is correct |
| 5 |
Correct |
6 ms |
6996 KB |
Output is correct |
| 6 |
Correct |
6 ms |
6976 KB |
Output is correct |
| 7 |
Correct |
6 ms |
6996 KB |
Output is correct |
| 8 |
Correct |
1022 ms |
12000 KB |
Output is correct |
| 9 |
Correct |
1044 ms |
11936 KB |
Output is correct |
