#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int MAXN = 1e5+10;
const int INF = 1e9;
typedef pair<ll,ll> pii;
int val[MAXN];
struct node {
int l, r, mid; ll sum, cnt;
node *le, *ri;
void bd(int l2, int r2){
l = l2; r = r2; mid = (l+r)/2;
sum = 0; cnt = 0;
if(l==r) return;
le = new node(); le->bd(l, mid);
ri = new node(); ri->bd(mid+1, r);
}
ll que(int w){
if(w<=0) return 0;
if(cnt <= w) return sum;
if(l == r) return 1ll*val[l]*w;
if(ri->cnt >= w) return ri->que(w);
return le->que(w - ri->cnt) + ri->que(ri->cnt);
}
pii upd(int x, int p){
if(r<x || x<l) return {sum, cnt};
if(l==r && l==x){
sum += 1ll*val[x]*p; cnt += p;
return {sum, cnt};
}
pii lupd = le->upd(x, p); pii rupd = ri->upd(x, p);
sum = lupd.fi + rupd.fi; cnt = lupd.se + rupd.se;
return {sum, cnt};
}
} A;
int n, sta, d;
int a[MAXN];
map<int,int> idx;
ll ret = 0;
int le = 1, ri = 0;
void setlr(int l,int r){
while(le < l){
A.upd(idx[a[le++]], -1);
} //mid-1, out
while(le > l){
A.upd(idx[a[--le]], 1);
} //mid, in
while(ri < r){
A.upd(idx[a[++ri]], 1);
} //optl, in
while(ri > r){
A.upd(idx[a[ri--]], -1);
} //optr+1, out
}
void solve(int l, int r, int optl, int optr){
if(l > r) return;
int mid = (l+r)/2, opt;
ll dp = -INF; //cari value mid
// mid - le udh ke build
if(ri-optl <= optr-ri){
for(int i=optl; i<=optr; i++){
setlr(mid,i);
// mid - i
// d-(sta-mid)-(i-mid)
ll can = A.que(d-sta + 2*mid - i);
//cout << mid << ' ' << i << ' ' << can << "que\n";
if(dp < can){
dp = can;
opt = i;
}
}
solve(mid+1, r, opt, optr); solve(l, mid-1, optl, opt);
} else {
for(int i=optr; i>=optl; i--){
setlr(mid,i);
ll can = A.que(d-sta + 2*mid - i);
//cout << mid << ' ' << i << ' ' << can << "que\n";
if(dp <= can){
dp = can;
opt = i;
}
}
solve(l, mid-1, optl, opt); solve(mid+1, r, opt, optr);
}
//cout << mid << ' '<< opt << ' ' << dp << "dp\n";
ret = max(ret, dp);
}
long long int findMaxAttraction(int N, int start, int D, int X[]) {
n = N; sta = start; d = D;
sta++;
set <int> s;
for(int i=0; i<=n-1; i++){
a[i+1] = X[i];
s.insert(a[i+1]);
}
int index = 0;
for(auto in : s){
idx[in] = ++index;
val[index] = in;
//cout << in << ' ' << index << "ind\n";
}
//cout << "\nA\n";
le = sta; ri = sta-1;
A.bd(1, MAXN);
solve(1, sta, sta, n);
for(int i=1; i<n-i+1; i++) swap(a[i], a[n-i+1]);
sta = n-sta+1;
//cout << "\nB\n";
le = sta; ri = sta-1;
A.bd(1, MAXN);
solve(1, sta, sta, n);
return ret;
}
Compilation message
holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:90:42: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
90 | solve(l, mid-1, optl, opt); solve(mid+1, r, opt, optr);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
25744 KB |
Output is correct |
2 |
Correct |
19 ms |
25684 KB |
Output is correct |
3 |
Correct |
20 ms |
25668 KB |
Output is correct |
4 |
Correct |
20 ms |
25684 KB |
Output is correct |
5 |
Correct |
28 ms |
25632 KB |
Output is correct |
6 |
Correct |
21 ms |
25680 KB |
Output is correct |
7 |
Correct |
20 ms |
25692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
125 ms |
26324 KB |
Output is correct |
2 |
Correct |
147 ms |
26200 KB |
Output is correct |
3 |
Correct |
137 ms |
26444 KB |
Output is correct |
4 |
Correct |
118 ms |
26216 KB |
Output is correct |
5 |
Correct |
161 ms |
26364 KB |
Output is correct |
6 |
Correct |
64 ms |
25936 KB |
Output is correct |
7 |
Correct |
96 ms |
26088 KB |
Output is correct |
8 |
Correct |
111 ms |
26160 KB |
Output is correct |
9 |
Correct |
46 ms |
25876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
26064 KB |
Output is correct |
2 |
Correct |
22 ms |
25680 KB |
Output is correct |
3 |
Correct |
26 ms |
25964 KB |
Output is correct |
4 |
Correct |
35 ms |
25932 KB |
Output is correct |
5 |
Correct |
33 ms |
25932 KB |
Output is correct |
6 |
Correct |
23 ms |
25856 KB |
Output is correct |
7 |
Correct |
24 ms |
25788 KB |
Output is correct |
8 |
Correct |
26 ms |
25676 KB |
Output is correct |
9 |
Correct |
23 ms |
25684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
125 ms |
26892 KB |
Output is correct |
2 |
Correct |
272 ms |
36760 KB |
Output is correct |
3 |
Correct |
732 ms |
30588 KB |
Output is correct |
4 |
Correct |
43 ms |
25956 KB |
Output is correct |
5 |
Correct |
25 ms |
25676 KB |
Output is correct |
6 |
Correct |
25 ms |
25676 KB |
Output is correct |
7 |
Correct |
29 ms |
25672 KB |
Output is correct |
8 |
Correct |
2582 ms |
35688 KB |
Output is correct |
9 |
Correct |
2645 ms |
35560 KB |
Output is correct |