#include "holiday.h"
#include <bits/stdc++.h>
#define max_n 1<<17
#define ll long long
using namespace std;
typedef pair<ll,int> li;
int n, d, start, L, R;
ll res;
pair<ll,int> segment[max_n<<1];
int id[max_n];
int ord[max_n];
int a[max_n];
ll get(int x) {
int k = 1;
ll sum = 0;
while(x < n) {
if(segment[k+k+1].second >= x) k = k+k+1;
else {
x -= segment[k+k+1].second;
sum += segment[k+k+1].first;
k>>=1;
}
}
sum += (x > 0) * segment[k].first;
return sum;
}
void add(int x) {
segment[x+max_n] = make_pair(a[ord[x]],1);
x+= max_n;
x>>=1;
for(;x>1;x>>=1) {
segment[x].first = segment[x+x].first + segment[x+x+1].first;
segment[x].second = segment[x+x].second + segment[x+x+1].second;
}
}
void erase(int x) {
segment[x+max_n] = make_pair(0,0);
x+=max_n;
x>>=1;
for(;x>1;x>>=1) {
segment[x].first = segment[x+x].first + segment[x+x+1].first;
segment[x].second = segment[x+x].second + segment[x+x+1].second;
}
}
void fix(int l, int r) {
while(l>L) erase(id[L++]);
while(r<R) erase(id[R--]);
while(l<L) add(id[--L]);
while(r>R) add(id[++R]);
}
bool cmp(int x, int y) {
return a[x]<a[y];
}
void solve(int l, int r, int sl, int sr) {
if(l>r) return;
int mid = (l+r)>>1;
for(int i = sl; i<=sr; i++) {
if(i>mid) break;
fix(i,mid);
ll tmp = get(d-(mid-i)-(mid-start));
res = max(res, tmp);
}
solve(l, mid-1, sl,sr);
solve(mid+1,r,sl,sr);
}
void solveStart(void) {
for(int i=1; i<=n; i++) ord[i] = i;
sort(ord+1, ord+n+1, cmp);
for(int i = 1; i <= n; i++)
id[ord[i]] = i;
L = 1;
R = 0;
memset(segment, 0, sizeof(segment));
for(int i = start; i <= n; i++) {
add(id[i]);
res = max(res, get(d - (i - start)));
}
memset(segment, 0, sizeof(segment));
solve(start, n, 1, start);
}
long long int findMaxAttraction(int N, int Start, int D, int attraction[]) {
n = N, d = D, start = Start+1;
for (int i = 0; i < N; ++i)
{
a[i+1] = attraction[i];
ord[i+1] = i+1;
}
solveStart();
reverse(a+1, a+n+1);
solveStart();
start = n - start + 1;
return res;
}
Compilation message
holiday.cpp: In function 'void add(int)':
holiday.cpp:29:11: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
segment[x+max_n] = make_pair(a[ord[x]],1);
^
holiday.cpp: In function 'void erase(int)':
holiday.cpp:38:11: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
segment[x+max_n] = make_pair(0,0);
^
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
int i, n_s;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
7928 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
7924 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
7924 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
7920 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
