#include"holiday.h"
#include "bits/stdc++.h"
long long frontR[300010];
long long frontB[300010];
long long backR[300010];
long long backB[300010];
std :: vector <int> P, Q;
std :: vector <int> CP, CQ;
std :: vector <int> RP, RQ;
int t[100010 * 4];
long long sum[100010 * 4];
int N;
bool cmp1(int x, int y) {
return P[x] < P[y];
}
bool cmp2(int x, int y) {
return Q[x] < Q[y];
}
void update(int x, long long val, int c = 1, int b = 0, int e = N) {
if(b == e) {
t[c] = 1;
sum[c] = val;
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(x <= m) update(x, val, l, b, m);
else update(x, val, r, m+1, e);
t[c] = t[l] + t[r];
sum[c] = sum[l] + sum[r];
}
void del(int x, int c = 1, int b = 0, int e = N) {
if(b == e) {
t[c] = sum[c] = 0;
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(x <= m) del(x, l, b, m);
else del(x, r, m+1, e);
t[c] = t[l] + t[r];
sum[c] = sum[l] + sum[r];
}
long long query(int take, int c = 1, int b = 0, int e = N) {
if(b == e) {
if(take > 0) return sum[c];
else return 0;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(t[r] >= take) return query(take, r, m+1, e);
else return query(take - t[r], l, b, m) + sum[r];
}
void solveFrontR(int l, int r, int b, int e) {
if(l > r) return ;
int m = (l + r) >> 1;
int opt = b;
long long best = -1;
for(int i = b; i <= e; i++) {
update(RP[i], P[i]);
long long o = query(m - (i + 1));
if(o > best) {
best = o;
opt = i;
}
}
for(int i = opt; i <= e; i++) {
del(RP[i]);
}
solveFrontR(m + 1, r, opt, e);
for(int i = b; i < opt; i++) {
del(RP[i]);
}
solveFrontR(l, m - 1, b, opt);
frontR[m] = std :: max(frontR[m], best);
}
void solveFrontB(int l, int r, int b, int e) {
if(l > r) return ;
int m = (l + r) >> 1;
int opt = b;
long long best = -1;
for(int i = b; i <= e; i++) {
update(RP[i], P[i]);
long long o = query(m - 2 * (i + 1));
if(o > best) {
best = o;
opt = i;
}
}
for(int i = opt; i <= e; i++) {
del(RP[i]);
}
solveFrontB(m + 1, r, opt, e);
for(int i = b; i < opt; i++) {
del(RP[i]);
}
solveFrontB(l, m - 1, b, opt);
frontB[m] = std :: max(frontB[m], best);
}
void solveBackR(int l, int r, int b, int e) {
if(l > r) return ;
int m = (l + r) >> 1;
int opt = b;
long long best = -1;
for(int i = b; i <= e; i++) {
update(RQ[i], Q[i]);
long long o = query(m - (i + 1));
if(o > best) {
best = o;
opt = i;
}
}
for(int i = opt; i <= e; i++) {
del(RQ[i]);
}
solveBackR(m + 1, r, opt, e);
for(int i = b; i < opt; i++) {
del(RQ[i]);
}
solveBackR(l, m - 1, b, opt);
backR[m] = std :: max(backR[m], best);
}
void solveBackB(int l, int r, int b, int e) {
if(l > r) return ;
int m = (l + r) >> 1;
int opt = b;
long long best = -1;
for(int i = b; i <= e; i++) {
update(RQ[i], Q[i]);
long long o = query(m - 2 * (i + 1));
if(o > best) {
best = o;
opt = i;
}
}
for(int i = opt; i <= e; i++) {
del(RQ[i]);
}
solveBackB(m + 1, r, opt, e);
for(int i = b; i < opt; i++) {
del(RQ[i]);
}
solveBackB(l, m - 1, b, opt);
backB[m] = std :: max(backB[m], best);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
for(int i = 0; i < start; i++) {
P.push_back(attraction[i]);
}
for(int i = start + 1; i < n; i++) {
Q.push_back(attraction[i]);
}
N = n;
RP.resize(n);
RQ.resize(n);
std :: reverse(P.begin(), P.end());
for(size_t i = 0; i < P.size(); i++) CP.push_back(i);
for(size_t i = 0; i < Q.size(); i++) CQ.push_back(i);
std :: sort(CP.begin(), CP.end(), cmp1);
std :: sort(CQ.begin(), CQ.end(), cmp2);
for(size_t i = 0; i < CP.size(); i++) RP[CP[i]] = i;
for(size_t i = 0; i < CQ.size(); i++) RQ[CQ[i]] = i;
if(!P.empty()) {
solveFrontR(1, d, 0, P.size() - 1);
solveFrontB(1, d, 0, P.size() - 1);
}
if(!Q.empty()) {
solveBackR(1, d, 0, Q.size() - 1);
solveBackB(1, d, 0, Q.size() - 1);
}
long long ans = 0;
for(int i = 0; i < d; i++) {
ans = std :: max(ans, frontB[i] + attraction[start] + backR[d - i - 1]);
ans = std :: max(ans, frontR[d - i - 1] + attraction[start] + backB[i]);
}
for(int i = 0; i <= d; i++) {
ans = std :: max(ans, frontB[i] + backR[d - i]);
ans = std :: max(ans, frontR[d - i] + backB[i]);
}
return ans;
}
Compilation message
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 |
Correct |
0 ms |
16360 KB |
Output is correct |
| 2 |
Correct |
0 ms |
16360 KB |
Output is correct |
| 3 |
Correct |
0 ms |
16356 KB |
Output is correct |
| 4 |
Correct |
0 ms |
16360 KB |
Output is correct |
| 5 |
Correct |
0 ms |
16356 KB |
Output is correct |
| 6 |
Correct |
0 ms |
16356 KB |
Output is correct |
| 7 |
Correct |
0 ms |
16356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1169 ms |
18764 KB |
Output is correct |
| 2 |
Correct |
1163 ms |
18760 KB |
Output is correct |
| 3 |
Correct |
1286 ms |
18764 KB |
Output is correct |
| 4 |
Correct |
1199 ms |
18768 KB |
Output is correct |
| 5 |
Correct |
1556 ms |
18700 KB |
Output is correct |
| 6 |
Correct |
483 ms |
16920 KB |
Output is correct |
| 7 |
Correct |
843 ms |
17612 KB |
Output is correct |
| 8 |
Correct |
1018 ms |
17700 KB |
Output is correct |
| 9 |
Correct |
333 ms |
16852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
16488 KB |
Output is correct |
| 2 |
Correct |
26 ms |
16488 KB |
Output is correct |
| 3 |
Correct |
19 ms |
16492 KB |
Output is correct |
| 4 |
Correct |
23 ms |
16488 KB |
Output is correct |
| 5 |
Correct |
16 ms |
16364 KB |
Output is correct |
| 6 |
Correct |
3 ms |
16364 KB |
Output is correct |
| 7 |
Correct |
3 ms |
16360 KB |
Output is correct |
| 8 |
Correct |
3 ms |
16360 KB |
Output is correct |
| 9 |
Correct |
3 ms |
16360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1286 ms |
18768 KB |
Output is correct |
| 2 |
Correct |
1189 ms |
18764 KB |
Output is correct |
| 3 |
Correct |
549 ms |
17112 KB |
Output is correct |
| 4 |
Correct |
13 ms |
16496 KB |
Output is correct |
| 5 |
Correct |
3 ms |
16360 KB |
Output is correct |
| 6 |
Correct |
3 ms |
16360 KB |
Output is correct |
| 7 |
Correct |
3 ms |
16360 KB |
Output is correct |
| 8 |
Correct |
1453 ms |
18512 KB |
Output is correct |
| 9 |
Correct |
1543 ms |
18516 KB |
Output is correct |
