#include "holiday.h"
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <queue>
#include <set>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int n;
int a[MAXN];
std::unordered_map <int,int> mp;
std::mt19937 mt(69420);
struct Treap
{
struct Node
{
int x, y;
int sz;
llong sumX;
Node *left, *right;
Node()
{
left = right = nullptr;
}
Node(int _x, int _y)
{
x = _x;
y = _y;
sz = 1;
sumX = x;
left = right = nullptr;
}
};
Node *root;
Node *pNode[MAXN];
void recover(Node *curr)
{
if (curr == nullptr)
{
return;
}
curr->sz = 1;
curr->sumX = curr->x;
if (curr->left != nullptr)
{
curr->sz += curr->left->sz;
curr->sumX += curr->left->sumX;
}
if (curr->right != nullptr)
{
curr->sz += curr->right->sz;
curr->sumX += curr->right->sumX;
}
}
void splitSIZE(Node *curr, Node *&left, Node *&right, int k)
{
if (curr == nullptr)
{
left = right = nullptr;
return;
}
int sz = 1;
if (curr->left != nullptr)
{
sz += curr->left->sz;
}
if (k >= sz)
{
left = curr;
splitSIZE(curr->right, left->right, right, k - sz);
recover(left);
} else
{
right = curr;
splitSIZE(curr->left, left, right->left, k);
recover(right);
}
}
void splitVALUE(Node *curr, Node *&left, Node *&right, int k)
{
if (curr == nullptr)
{
left = right = nullptr;
return;
}
if (curr->x < k)
{
left = curr;
splitVALUE(curr->right, left->right, right, k);
recover(left);
} else
{
right = curr;
splitVALUE(curr->left, left, right->left, k);
recover(right);
}
}
void merge(Node *&curr, Node *left, Node *right)
{
if (left == nullptr)
{
curr = right;
return;
}
if (right == nullptr)
{
curr = left;
return;
}
if (left->y > right->y)
{
curr = left;
merge(curr->right, left->right, right);
} else
{
curr = right;
merge(curr->left, left, right->left);
}
recover(curr);
}
void build()
{
for (int i = 1 ; i <= n ; ++i)
{
pNode[i] = new Node(a[i], mt());
}
}
void insert(int idx)
{
Node *l, *r;
splitVALUE(root, l, r, a[idx]);
merge(l, l, pNode[idx]);
merge(root, l, r);
}
void erase(int idx)
{
Node *l, *r, *nz;
splitVALUE(root, l, r, a[idx]);
splitSIZE(r, nz, r, 1);
std::swap(pNode[idx], nz);
merge(root, l, r);
}
llong findLargest(int k)
{
k = std::min(k, root->sz);
Node *left, *right;
splitSIZE(root, left, right, root->sz - k);
llong res = right->sumX;
merge(root, left, right);
return res;
}
std::vector <int> vals;
void printTreap(Node *curr)
{
if (curr == nullptr)
{
return;
}
vals.push_back(curr->x);
printTreap(curr->left);
printTreap(curr->right);
}
void printTreap()
{
vals.clear();
printTreap(root);
std::cout << "treap has\n";
for (const int &i : vals)
{
std::cout << i << ' ';
}
std::cout << '\n';
}
};
int pos, d;
llong ans;
Treap treap;
int moL = 1;
int moR = 0;
llong getCost(int l, int r)
{
while (moL > l) treap.insert(--moL);
while (moR < r) treap.insert(++moR);
while (moL < l) treap.erase(moL++);
while (moR > r) treap.erase(moR--);
return treap.findLargest(d - pos + 2 * l - r);
}
void rec(int l, int r, int optL, int optR)
{
if (d - pos + 2 * r - optL <= 0)
{
return;
}
int opt = -1;
int mid = (l + r) / 2;
llong currSum = 0;
llong currRes = 0;
for (int i = optL ; i <= optR && d - pos + 2 * mid - i > 0 ; ++i)
{
currSum = getCost(mid, i);
if (currSum > currRes)
{
opt = i;
currRes = currSum;
}
}
if (opt == -1)
{
opt = optL;
}
if (l < mid) rec(l, mid - 1, optL, opt);
if (mid < r) rec(mid + 1, r, opt, optR);
ans = std::max(ans, currRes);
}
llong findMaxAttraction(int N, int start, int D, int A[])
{
n = N;
d = D;
pos = start + 1;
for (int i = 1 ; i <= n ; ++i)
{
a[i] = A[i - 1];
}
int cnt = 0;
for (int i = 1 ; i <= n ; ++i)
{
if (!mp.count(a[i]))
{
mp[a[i]] = ++cnt;
}
}
treap.build();
if (pos <= n)
{
rec(1, pos, pos + 1, n);
}
std::reverse(a + 1, a + 1 + n);
pos = n - pos + 1;
treap.root = nullptr;
treap.build();
moL = 1;
moR = 0;
if (pos <= n)
{
rec(1, pos, pos + 1, n);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
0 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
0 ms |
596 KB |
Output is correct |
| 6 |
Correct |
0 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
11240 KB |
Output is correct |
| 2 |
Correct |
150 ms |
11236 KB |
Output is correct |
| 3 |
Correct |
192 ms |
11236 KB |
Output is correct |
| 4 |
Correct |
148 ms |
11160 KB |
Output is correct |
| 5 |
Correct |
277 ms |
10364 KB |
Output is correct |
| 6 |
Correct |
85 ms |
3764 KB |
Output is correct |
| 7 |
Correct |
171 ms |
6072 KB |
Output is correct |
| 8 |
Correct |
170 ms |
7204 KB |
Output is correct |
| 9 |
Correct |
58 ms |
2760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
3 ms |
980 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
22 ms |
1132 KB |
Output is correct |
| 5 |
Correct |
19 ms |
1092 KB |
Output is correct |
| 6 |
Correct |
4 ms |
724 KB |
Output is correct |
| 7 |
Correct |
5 ms |
724 KB |
Output is correct |
| 8 |
Correct |
5 ms |
724 KB |
Output is correct |
| 9 |
Correct |
5 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
11168 KB |
Output is correct |
| 2 |
Correct |
125 ms |
15648 KB |
Output is correct |
| 3 |
Correct |
244 ms |
7456 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
4 ms |
796 KB |
Output is correct |
| 6 |
Correct |
5 ms |
724 KB |
Output is correct |
| 7 |
Correct |
5 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1799 ms |
16188 KB |
Output is correct |
| 9 |
Correct |
1754 ms |
16196 KB |
Output is correct |
