#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
ll N, S, D, res;
ll ST[400005], cur[400005];
ll A[400005], P[400005], Pr[400005], Sf[400005];
ll X[400005], Y[400005];
pair<ll, ll> C[400005];
void update(ll v, ll l, ll r, ll p, ll val) {
if(l == r) {
ST[v] = val;
cur[v] = (val > 0);
return;
}
ll md = (l + r) / 2;
if(p <= md) update(v * 2, l, (l + r) / 2, p, val);
else update(v * 2 + 1, (l + r) / 2 + 1, r, p, val);
ST[v] = ST[v * 2] + ST[v * 2 + 1];
cur[v] = cur[v * 2] + cur[v * 2 + 1];
}
long long query(ll v, ll l, ll r, ll p) {
if(cur[v] == p) return ST[v];
ll md = (l + r) / 2;
if(p <= cur[v * 2])
return query(v * 2, l, (l + r) / 2, p);
return query(v * 2, l, (l + r) / 2, cur[v * 2])
+ query(v * 2 + 1, (l + r) / 2 + 1, r, p - cur[v * 2]);
}
long long query0(ll v, ll l, ll r, ll p) {
if(cur[v] == p) return ST[v];
ll md = (l + r) / 2;
if(p <= cur[v * 2 + 1])
return query0(v * 2 + 1, (l + r) / 2 + 1, r, p);
return query0(v * 2, l, (l + r) / 2, p - cur[v * 2 + 1])
+ query0(v * 2 + 1, (l + r) / 2 + 1, r, cur[v * 2 + 1]);
}
void solve(ll i, ll j, ll lo, ll hi) {
if(i > j) return;
ll md = (i + j) / 2;
for(ll l = lo; l <= hi; l++) {
update(1, S, N - 1, P[l], A[l]);
if(md - l + S > 0) {
long long ans = query(1, S, N - 1, min(cur[1], md - l + S));
if(Pr[md] < ans) {
Pr[md] = ans; X[md] = l;
}
}
}
for(ll l = lo; l <= hi; l++)
update(1, S, N - 1, P[l], 0);
solve(i, md - 1, lo, X[md]);
solve(md + 1, j, X[md], hi);
for(ll l = lo; l <= hi; l++)
update(1, S, N - 1, P[l], A[l]);
}
void solve0(ll i, ll j, ll lo, ll hi) {
if(i > j) return;
ll md = (i + j) / 2;
for(ll l = hi; l >= lo; l--) {
update(1, 0, S - 1, P[l], A[l]);
if(md - S + 1 + l > 0) {
long long ans = query0(1, 0, S - 1, min(cur[1], md - S + 1 + l));
if(Sf[md] < ans) {
Sf[md] = ans; Y[md] = l;
}
}
}
for(ll l = lo; l <= hi; l++)
update(1, 0, S - 1, P[l], 0);
solve0(i, md - 1, Y[md], hi);
solve0(md + 1, j, lo, Y[md]);
for(ll l = lo; l <= hi; l++)
update(1, 0, S - 1, P[l], A[l]);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n, S = start, D = d;
for(ll l = 0; l < N; l++) {
A[l] = attraction[l];
C[l] = {A[l], l};
}
sort(C, C + start); sort(C + start, C + N);
reverse(C + start, C + N);
for(ll l = 0; l < N; l++)
P[C[l].second] = l;
for(ll l = 0; l <= D; l++)
X[l] = S, Y[l] = S - 1;
if(start < N) solve(1, D, start, N - 1);
for(ll l = 0; l <= 4 * N; l++) ST[l] = cur[l] = 0;
if(start > 0) solve0(1, D, 0, start - 1);
res = max(Pr[D], Sf[D - 1]);
for(ll l = 0; l <= D; l++) {
if(D - l - X[l] + S - 1 >= 0)
res = max(res, Pr[l] + Sf[D - l - X[l] + S - 1]);
if(D - l - S + Y[l] - 1 >= 0)
res = max(res, Sf[l] + Pr[D - l - S + Y[l] - 1]);
}
return res;
}
Compilation message
holiday.cpp: In function 'long long int query(ll, ll, ll, ll)':
holiday.cpp:34:20: warning: unused variable 'md' [-Wunused-variable]
34 | ll md = (l + r) / 2;
| ^~
holiday.cpp: In function 'long long int query0(ll, ll, ll, ll)':
holiday.cpp:42:20: warning: unused variable 'md' [-Wunused-variable]
42 | ll md = (l + r) / 2;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
710 ms |
14692 KB |
Output is correct |
| 2 |
Correct |
657 ms |
13140 KB |
Output is correct |
| 3 |
Correct |
707 ms |
14796 KB |
Output is correct |
| 4 |
Correct |
674 ms |
14784 KB |
Output is correct |
| 5 |
Correct |
870 ms |
12328 KB |
Output is correct |
| 6 |
Correct |
271 ms |
7680 KB |
Output is correct |
| 7 |
Correct |
490 ms |
7552 KB |
Output is correct |
| 8 |
Correct |
547 ms |
8496 KB |
Output is correct |
| 9 |
Correct |
211 ms |
8164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
15 ms |
1240 KB |
Output is correct |
| 3 |
Correct |
16 ms |
1232 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1112 KB |
Output is correct |
| 6 |
Correct |
4 ms |
832 KB |
Output is correct |
| 7 |
Correct |
3 ms |
852 KB |
Output is correct |
| 8 |
Correct |
3 ms |
852 KB |
Output is correct |
| 9 |
Correct |
3 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
695 ms |
17940 KB |
Output is correct |
| 2 |
Correct |
756 ms |
15960 KB |
Output is correct |
| 3 |
Correct |
278 ms |
5272 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1076 KB |
Output is correct |
| 5 |
Correct |
3 ms |
852 KB |
Output is correct |
| 6 |
Correct |
3 ms |
852 KB |
Output is correct |
| 7 |
Correct |
3 ms |
832 KB |
Output is correct |
| 8 |
Correct |
850 ms |
12528 KB |
Output is correct |
| 9 |
Correct |
828 ms |
12408 KB |
Output is correct |
