#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define REP0(i, n) for(int i = 0, _n = (n); i < _n; ++i)
#define REP1(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define REPB0(i, n) for(int i = (n) - 1; i >= 0; --i)
#define REPB1(i, n) for(int i = (n); i > 0; --i)
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORB(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define X first
#define Y second
using namespace std;
typedef pair<ll, int> li;
const int N = 100001, D = 2*N + N/2;
int n, s, d, sz, lg, arr[N], val[N];
ll R[D], RR[D], L[D], LL[D];
li fen[N];
void compress()
{
set<int> s(arr + 1, arr + n + 1);
vector<int> tmp(s.begin(), s.end());
sz = tmp.size();
lg = 32 - __builtin_clz(sz) - 1;
int v;
REP1(i, n) {
v = sz - (lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin());
val[v] = arr[i];
arr[i] = v;
}
}
void update(int pos)
{
for(int i = pos; i <= sz; i += i&-i) {
fen[i].X += val[pos];
++fen[i].Y;
}
}
void rollback(int pos)
{
for(int i = pos; i <= sz; i += i&-i) {
fen[i].X -= val[pos];
--fen[i].Y;
}
}
li binsearch(int value)
{
int p = 0, v = 0, jump;
REPB0(i, lg + 1) {
jump = p + (1 << i);
if(jump <= sz && v + fen[jump].Y < value) {
p = jump;
v += fen[p].Y;
}
}
if(p == sz) return {0, p};
return {(value - v) * (ll)val[p + 1], p};
}
ll getSum(int pos)
{
ll sum = 0;
for(int i = pos; i; i &= i - 1)
sum += fen[i].X;
return sum;
}
void solveR(ll l, ll r, int from, int to)
{
if(l > r) return;
int pos = from, last = to + 1, mid = l + r >> 1;
li p;
ll res = -1, cur;
FOR(i, from, to) {
if(i - s >= mid) {
last = i;
break;
}
update(arr[i]);
p = binsearch(mid - i + s);
cur = p.X + getSum(p.Y);
if(cur > res) {
res = cur;
pos = i;
}
}
if(res != -1) R[mid] = res;
FOR(i, pos, min(to, last - 1)) rollback(arr[i]);
solveR(mid + 1, r, pos, to);
FOR(i, from, pos - 1) rollback(arr[i]);
solveR(l, mid - 1, from, pos);
}
void solveRR(int l, int r, int from, int to)
{
if(l > r) return;
int pos = from, last = to + 1, mid = l + r >> 1;
li p;
ll res = -1, cur;
FOR(i, from, to) {
if(2*(i - s) >= mid) {
last = i;
break;
}
update(arr[i]);
p = binsearch(mid - 2*(i - s));
cur = p.X + getSum(p.Y);
if(cur > res) {
res = cur;
pos = i;
}
}
if(res != -1) RR[mid] = res;
FOR(i, pos, min(last - 1, to)) rollback(arr[i]);
solveRR(mid + 1, r, pos, to);
FOR(i, from, pos - 1) rollback(arr[i]);
solveRR(l, mid - 1, from, pos);
}
void solveL(int l, int r, int from, int to)
{
if(l > r) return;
int pos = to, last = from - 1, mid = l + r >> 1;
li p;
ll res = -1, cur;
FORB(i, to, from) {
if(s - i >= mid) {
last = i;
break;
}
update(arr[i]);
p = binsearch(mid - s + i);
cur = p.X + getSum(p.Y);
if(cur > res) {
res = cur;
pos = i;
}
}
if(res != -1) L[mid] = res;
FOR(i, max(last + 1, from), pos) rollback(arr[i]);
solveL(mid + 1, r, from, pos);
FOR(i, pos + 1, to) rollback(arr[i]);
solveL(l, mid - 1, pos, to);
}
void solveLL(int l, int r, int from, int to)
{
if(l > r) return;
int pos = to, last = from - 1, mid = l + r >> 1;
li p;
ll res = -1, cur;
FORB(i, to, from) {
if(2*(s - i) >= mid) {
last = i;
break;
}
update(arr[i]);
p = binsearch(mid - 2*(s - i));
cur = p.X + getSum(p.Y);
if(cur > res) {
res = cur;
pos = i;
}
}
if(res != -1) LL[mid] = res;
FOR(i, max(last + 1, from), pos) rollback(arr[i]);
solveLL(mid + 1, r, from, pos);
FOR(i, pos + 1, to) rollback(arr[i]);
solveLL(l, mid - 1, pos, to);
}
long long int findMaxAttraction(int nn, int start, int dd, int attraction[]) {
n = nn;
s = start + 1;
d = dd;
REP1(i, n) arr[i] = attraction[i - 1];
compress();
solveR(1, d, s, n);
solveRR(1, d, s, n);
if(s > 1) {
solveL(2, d, 1, s - 1);
solveLL(2, d, 1, s - 1);
}
long long int ans = 0;
REP0(t, d + 1) {
ans = max(ans, L[t] + RR[d - t]);
ans = max(ans, LL[t] + R[d - t]);
}
return ans;
}
Compilation message
holiday.cpp: In function 'void solveR(long long int, long long int, int, int)':
holiday.cpp:70:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int pos = from, last = to + 1, mid = l + r >> 1;
| ~~^~~
holiday.cpp: In function 'void solveRR(int, int, int, int)':
holiday.cpp:95:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
95 | int pos = from, last = to + 1, mid = l + r >> 1;
| ~~^~~
holiday.cpp: In function 'void solveL(int, int, int, int)':
holiday.cpp:120:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
120 | int pos = to, last = from - 1, mid = l + r >> 1;
| ~~^~~
holiday.cpp: In function 'void solveLL(int, int, int, int)':
holiday.cpp:145:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
145 | int pos = to, last = from - 1, mid = l + r >> 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
63 ms |
4472 KB |
Output is correct |
| 2 |
Correct |
60 ms |
4600 KB |
Output is correct |
| 3 |
Correct |
84 ms |
4472 KB |
Output is correct |
| 4 |
Correct |
67 ms |
4472 KB |
Output is correct |
| 5 |
Correct |
186 ms |
3320 KB |
Output is correct |
| 6 |
Correct |
84 ms |
3448 KB |
Output is correct |
| 7 |
Correct |
113 ms |
2296 KB |
Output is correct |
| 8 |
Correct |
123 ms |
2300 KB |
Output is correct |
| 9 |
Correct |
75 ms |
4348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
896 KB |
Output is correct |
| 2 |
Correct |
3 ms |
640 KB |
Output is correct |
| 3 |
Correct |
11 ms |
896 KB |
Output is correct |
| 4 |
Correct |
10 ms |
768 KB |
Output is correct |
| 5 |
Correct |
9 ms |
640 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
85 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
729 ms |
12544 KB |
Output is correct |
| 3 |
Correct |
105 ms |
4412 KB |
Output is correct |
| 4 |
Correct |
6 ms |
640 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
535 ms |
9476 KB |
Output is correct |
| 9 |
Correct |
527 ms |
9360 KB |
Output is correct |
