/*
F@CK YOU PERSISTENT DATA STRUCTURE
F@CK YOU SEGMENT TREE
F@CK MLE
NO POINTER PERSISTENT SEGMENT TREE CHALLENGE?
*/
#include <bits/stdc++.h>
#include "holiday.h"
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 2;
const int maxD = 3e5;
int n;
int node_cnt;
vector <ll> node;
struct __attribute__((packed)) TNode{
int lp, rp;
int val;
ll sum;
TNode(){};
TNode(int _val, ll _sum) : lp(0), rp(0), val(_val), sum(_sum){}
TNode(const TNode &left, const TNode &right){
val = left.val + right.val;
sum = left.sum + right.sum;
}
};
TNode st[maxN * 25];
ll p[maxN];
pll ls[maxD];
pll rs[maxD];
int Start;
void build(int id, int i, int l = 1, int r = node.size()){
if (l == r){
if (l == i) st[id] = {1, node[i - 1]};
else st[id] = {0, 0};
return;
}
int mid = (l + r) / 2;
int lp = ++node_cnt;
build(lp, i, l, mid);
int rp = ++node_cnt;
build(rp, i, mid + 1, r);
st[id] = {st[lp], st[rp]};
st[id].lp = lp;
st[id].rp = rp;
}
void update(int id, int last, int i, int l = 1, int r = node.size()){
if (l == r){
st[id] = {st[last].val + 1, st[last].sum + node[l - 1]};
return;
}
int mid = (l + r) / 2;
if (i <= mid){
int lp = ++node_cnt;
update(lp, st[last].lp, i, l, mid);
st[id] = {st[lp], st[st[last].rp]};
st[id].lp = lp;
st[id].rp = st[last].rp;
}
else{
int rp = ++node_cnt;
update(rp, st[last].rp, i, mid + 1, r);
st[id] = {st[st[last].lp], st[rp]};
st[id].rp = rp;
st[id].lp = st[last].lp;
}
}
ll get(int id, int k, int l = 1, int r = node.size()){
if (l == r){
return k * node[l - 1];
}
int mid = (l + r) / 2;
if (st[st[id].rp].val >= k) return get(st[id].rp, k, mid + 1, r);
else return st[st[id].rp].sum + get(st[id].lp, k - st[st[id].rp].val, l, mid);
}
inline int pos(int i){
return upper_bound(node.begin(), node.end(), i) - node.begin();
}
void DnCl(int s, int t, int l, int r){
if (l > r || s < t){
return;
}
int mid = (l + r) / 2;
for (int i = s; i >= t; --i){
ll tem = get(i, min(mid - (Start - i - 1), st[i].val));
if (tem > ls[mid].fi){
ls[mid].fi = tem;
ls[mid].se = i;
}
}
if (l == r) return;
DnCl(s, ls[mid].se, l, mid - 1);
DnCl(ls[mid].se, t, mid + 1, r);
}
void DnCr(int s, int t, int l, int r){
if (l > r || s > t){
return;
}
int mid = (l + r) / 2;
rs[mid].se = s;
for (int i = s; i <= t; ++i){
ll tem = get(i, min(mid - (i - Start), st[i].val));
if (tem > rs[mid].fi){
rs[mid].fi = tem;
rs[mid].se = i;
}
}
if (l == r) return;
DnCr(s, rs[mid].se, l, mid - 1);
DnCr(rs[mid].se, t, mid + 1, r);
}
ll findMaxAttraction(int N, int start, int d, int attraction[]){
n = N;
ll sum = 0;
for (int i = 0; i < n; ++i){
p[i + 1] = attraction[i];
node.pb(p[i + 1]);
sum += p[i + 1];
}
if (d == 0) return 0;
node.pb(0);
sort(node.begin(), node.end());
node.resize(unique(node.begin(), node.end()) - node.begin());
++start;
node_cnt = n;
build(start, pos(p[start]));
build(start - 1, pos(p[start - 1]));
for (int i = start + 1; i <= n; ++i){
update(i, i - 1, pos(p[i]));
}
for (int i = start - 2; i >= 1; --i){
st[i] = st[i + 1];
update(i, i + 1, pos(p[i]));
}
Start = start;
DnCr(start, n, 1, d);
DnCl(start - 1, 1, 1, d);
ll ans = ls[d - 1].fi;
for (int i = 1; i <= d; ++i){
int k = d - rs[i].se + start - 1 - i;
if (k < 0) ans = max(ans, rs[i].fi);
else ans = max(ans, ls[k].fi + rs[i].fi);
}
ans = max(ans, rs[d].fi);
for (int i = 1; i < d; ++i){
int k = d + ls[i].se - start - i - 1;
if (k < 0) ans = max(ans, ls[i].fi);
else{
ans = max(ans, ls[i].fi + rs[k].fi);
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
0 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
0 ms |
596 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
9440 KB |
Output is correct |
| 2 |
Correct |
23 ms |
7392 KB |
Output is correct |
| 3 |
Correct |
26 ms |
9448 KB |
Output is correct |
| 4 |
Correct |
24 ms |
9428 KB |
Output is correct |
| 5 |
Correct |
65 ms |
18124 KB |
Output is correct |
| 6 |
Correct |
29 ms |
8388 KB |
Output is correct |
| 7 |
Correct |
37 ms |
10660 KB |
Output is correct |
| 8 |
Correct |
47 ms |
12468 KB |
Output is correct |
| 9 |
Correct |
26 ms |
7872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2004 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
7 ms |
2004 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1708 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 6 |
Correct |
2 ms |
980 KB |
Output is correct |
| 7 |
Correct |
2 ms |
980 KB |
Output is correct |
| 8 |
Correct |
2 ms |
980 KB |
Output is correct |
| 9 |
Correct |
1 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
14112 KB |
Output is correct |
| 2 |
Correct |
293 ms |
48768 KB |
Output is correct |
| 3 |
Correct |
103 ms |
19880 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1620 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
852 KB |
Output is correct |
| 8 |
Correct |
303 ms |
45140 KB |
Output is correct |
| 9 |
Correct |
312 ms |
45020 KB |
Output is correct |
