#include"holiday.h"
#include "bits/stdc++.h"
long long frontR[100010];
long long frontB[100010];
long long backR[100010];
long long backB[100010];
std :: vector <int> P, Q;
std :: vector <int> CP, CQ;
std :: vector <int> RP, RQ;
bool cmpP(int x, int y) {
return P[x] < P[y];
}
bool cmpQ(int x, int y) {
return Q[x] < Q[y];
}
struct node {
node *l, *r;
long long sum;
int tot;
node () {
l = r = NULL;
sum = 0;
tot = 0;
}
void merge() {
sum = 0;
tot = 0;
if(l) {
sum += l -> sum;
tot += l -> tot;
}
if(r) {
sum += r -> sum;
tot += r -> tot;
}
}
} *t[100010], *s[100010];
typedef node* pnode;
void init(pnode &cur, int b, int e) {
cur = new node();
if(b == e) {
return ;
}
int m = (b + e) >> 1;
init(cur -> l, b, m);
init(cur -> r, m+1, e);
}
void insert(pnode &cur, pnode &prev, int pos, int cost, int b, int e) {
cur = new node();
if(b == e) {
cur -> tot = 1;
cur -> sum = cost;
return ;
}
int m = (b + e) >> 1;
if(pos <= m) {
cur -> r = prev -> r;
insert(cur -> l, prev -> l, pos, cost, b, m);
} else {
cur -> l = prev -> l;
insert(cur -> r, prev -> r, pos, cost, m+1, e);
}
cur -> merge();
}
long long query(pnode cur, int take, int b, int e) {
if(b == e) {
if(take > 0) return cur -> sum;
else return 0;
}
int m = (b + e) >> 1;
if(cur -> r -> tot >= take) return query(cur -> r, take, m + 1, e);
else return query(cur -> l, take - (cur -> r -> tot), b, m) + (cur -> r -> sum);
}
long long sortSumQ(int x, int take) {
if(take <= 0) return 0;
x++;
return query(s[x], take, 1, Q.size());
}
long long sortSumP(int x, int take) {
if(take <= 0) return 0;
x++;
return query(t[x], take, 1, P.size());
}
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++) {
long long o = sortSumP(i, m - (i + 1));
if(o > best) {
best = o;
opt = i;
}
}
solveFrontR(l, m - 1, b, opt);
solveFrontR(m + 1, r, opt, e);
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++) {
long long o = sortSumP(i, m - 2 * (i + 1));
if(o > best) {
best = o;
opt = i;
}
}
solveFrontB(l, m - 1, b, opt);
solveFrontB(m + 1, r, opt, e);
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++) {
long long o = sortSumQ(i, m - (i + 1));
if(o > best) {
best = o;
opt = i;
}
}
solveBackR(l, m - 1, b, opt);
solveBackR(m + 1, r, opt, e);
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++) {
long long o = sortSumQ(i, m - 2 * (i + 1));
if(o > best) {
best = o;
opt = i;
}
}
solveBackB(l, m - 1, b, opt);
solveBackB(m + 1, r, opt, e);
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]);
}
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(), cmpP);
std :: sort(CQ.begin(), CQ.end(), cmpQ);
RP.resize(n + 10);
RQ.resize(n + 10);
for(size_t i = 0; i < CP.size(); i++) {
RP[CP[i]] = i + 1;
}
for(size_t i = 0; i < CQ.size(); i++) {
RQ[CQ[i]] = i + 1;
}
if(!P.empty()) {
t[0] = NULL;
init(t[0], 1, P.size());
for(int i = 1; i <= P.size(); i++) {
t[i] = NULL;
insert(t[i], t[i - 1], RP[i-1], P[i-1], 1, P.size());
}
solveFrontR(1, d, 0, P.size() - 1);
solveFrontB(1, d, 0, P.size() - 1);
}
if(!Q.empty()) {
s[0] = NULL;
init(s[0], 1, Q.size());
for(int i = 1; i <= Q.size(); i++) {
s[i] = NULL;
insert(s[i], s[i - 1], RQ[i-1], Q[i-1], 1, Q.size());
}
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
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:183:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i <= P.size(); i++) {
^
holiday.cpp:193:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i <= Q.size(); i++) {
^
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 |
6984 KB |
Output is correct |
| 2 |
Correct |
0 ms |
6984 KB |
Output is correct |
| 3 |
Correct |
0 ms |
6988 KB |
Output is correct |
| 4 |
Correct |
0 ms |
6980 KB |
Output is correct |
| 5 |
Correct |
0 ms |
6984 KB |
Output is correct |
| 6 |
Correct |
0 ms |
6988 KB |
Output is correct |
| 7 |
Correct |
0 ms |
6984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
66 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9100 KB |
Output is correct |
| 2 |
Correct |
13 ms |
9096 KB |
Output is correct |
| 3 |
Correct |
16 ms |
9100 KB |
Output is correct |
| 4 |
Correct |
9 ms |
8832 KB |
Output is correct |
| 5 |
Correct |
9 ms |
8700 KB |
Output is correct |
| 6 |
Correct |
3 ms |
7648 KB |
Output is correct |
| 7 |
Correct |
0 ms |
7644 KB |
Output is correct |
| 8 |
Correct |
0 ms |
7640 KB |
Output is correct |
| 9 |
Correct |
0 ms |
7640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
89 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
