using namespace std;
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 100005
pair<long long,int> add(pair<long long,int> a,pair<long long,int> b) {
return make_pair(a.first + b.first,a.second + b.second);
}
int cnt;
struct node {
int lp,rp;
pair<long long,int> v;
} nodes[20 * MAXN];
int build_node(int l,int r) {
int owo = cnt;
node& uwu = nodes[cnt++] = node{-1,-1,{0,0}};
if(l == r) return owo;
int m = (l + r) >> 1;
uwu.lp = build_node(l,m);
uwu.rp = build_node(m + 1,r);
return owo;
}
int get_node(int lp,int rp) {
int owo = cnt;
node& uwu = nodes[cnt++] = node{lp,rp,add(nodes[lp].v,nodes[rp].v)};
return owo;
}
int get_node(pair<long long,int> v) {
int owo = cnt;
node& uwu = nodes[cnt++] = node{-1,-1,v};
return owo;
}
int upd(int p,int l,int r,int x,pair<long long,int> d) {
node& uwu = nodes[p];
if(l == r) return get_node(add(uwu.v,d));
int m = (l + r) >> 1;
if(x <= m) return get_node(upd(uwu.lp,l,m,x,d),uwu.rp);
return get_node(uwu.lp,upd(uwu.rp,m + 1,r,x,d));
}
int get(int p,int l,int r,int a,int b) {
node& uwu = nodes[p];
if(a > r || b < l) return 0;
if(a <= l && b >= r) return uwu.v.second;
int m = (l + r) >> 1;
return (a > m ? 0 : get(uwu.lp,l,m,a,b)) + (b < m ? 0 : get(uwu.rp,m + 1,r,a,b));
}
long long get2(int p,int l,int r,int a,int b) {
node& uwu = nodes[p];
if(a > r || b < l) return 0;
if(a <= l && b >= r) return uwu.v.first;
int m = (l + r) >> 1;
return get2(uwu.lp,l,m,a,b) + get2(uwu.rp,m + 1,r,a,b);
}
int st[MAXN];
int N,S,D;
pair<long long,int> dp[MAXN];
void solve1(int x,int y,int a,int b) {
if(x > y) return;
if((S - y) > (b - S)) return;
int z = (x + y) >> 1;
dp[z] = {-1,-1};
for(int i = a;i <= b;++i) {
int l = 0;
int r = N;
// if((S - z) > (i - S)) continue;
while(l < r) {
int m = (l + r + 1) >> 1;
if(get(st[m],0,N - 1,z,i) + (S - z) + (i - z) <= D) {
l = m;
}else{
r = m - 1;
}
}
dp[z] = max(dp[z],{get2(st[l],0,N - 1,z,i),-i});
}
if(x == y) return;
solve1(x,z - 1,a,-dp[z].second);
solve1(z + 1,y,-dp[z].second,b);
}
void solve2(int x,int y,int a,int b) {
if(x > y) return;
if((x - S) > (S - a)) return;
int z = (x + y) >> 1;
if(!dp[z].first) dp[z] = {-1,-1};
for(int i = a;i <= b;++i) {
int l = 0;
int r = N;
while(l < r) {
int m = (l + r + 1) >> 1;
if(get(st[m],0,N - 1,i,z) + (z - S) + (z - i) <= D) {
l = m;
}else{
r = m - 1;
}
}
dp[z] = max(dp[z],{get2(st[l],0,N - 1,i,z),i});
}
if(x == y) return;
solve2(x,z - 1,a,dp[z].second);
solve2(z + 1,y,dp[z].second,b);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n;
S = start;
D = d;
vector<pair<long long,int>> v;
for(int i = 0;i < N;++i) {
v.push_back({-attraction[i],i});
}
st[0] = build_node(0,N - 1);
sort(v.begin(),v.end());
for(int i = 0;i < N;++i) {
st[i + 1] = upd(st[i],0,N - 1,v[i].second,make_pair(-v[i].first,1));
}
solve1(0,S,S,N - 1);
solve2(S,N - 1,0,S);
long long ans = 0;
for(int i = 0;i < N;++i) {
ans = max(ans,dp[i].first);
}
return ans;
}
Compilation message
holiday.cpp: In function 'int get_node(int, int)':
holiday.cpp:32:8: warning: unused variable 'uwu' [-Wunused-variable]
32 | node& uwu = nodes[cnt++] = node{lp,rp,add(nodes[lp].v,nodes[rp].v)};
| ^~~
holiday.cpp: In function 'int get_node(std::pair<long long int, int>)':
holiday.cpp:38:8: warning: unused variable 'uwu' [-Wunused-variable]
38 | node& uwu = nodes[cnt++] = node{-1,-1,v};
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
47640 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47608 KB |
Output is correct |
| 3 |
Correct |
31 ms |
47644 KB |
Output is correct |
| 4 |
Correct |
29 ms |
47688 KB |
Output is correct |
| 5 |
Correct |
31 ms |
47604 KB |
Output is correct |
| 6 |
Correct |
22 ms |
47564 KB |
Output is correct |
| 7 |
Correct |
24 ms |
47560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
358 ms |
49888 KB |
Output is correct |
| 2 |
Correct |
254 ms |
49848 KB |
Output is correct |
| 3 |
Correct |
359 ms |
49812 KB |
Output is correct |
| 4 |
Correct |
209 ms |
49760 KB |
Output is correct |
| 5 |
Correct |
273 ms |
49856 KB |
Output is correct |
| 6 |
Correct |
151 ms |
48288 KB |
Output is correct |
| 7 |
Correct |
212 ms |
48912 KB |
Output is correct |
| 8 |
Correct |
226 ms |
49020 KB |
Output is correct |
| 9 |
Correct |
79 ms |
48196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
47748 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47760 KB |
Output is correct |
| 3 |
Correct |
31 ms |
47812 KB |
Output is correct |
| 4 |
Correct |
52 ms |
47772 KB |
Output is correct |
| 5 |
Correct |
69 ms |
47864 KB |
Output is correct |
| 6 |
Correct |
34 ms |
47676 KB |
Output is correct |
| 7 |
Correct |
31 ms |
47688 KB |
Output is correct |
| 8 |
Correct |
38 ms |
47824 KB |
Output is correct |
| 9 |
Correct |
41 ms |
47696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
197 ms |
49972 KB |
Output is correct |
| 2 |
Correct |
394 ms |
49816 KB |
Output is correct |
| 3 |
Correct |
2037 ms |
48828 KB |
Output is correct |
| 4 |
Correct |
67 ms |
47788 KB |
Output is correct |
| 5 |
Correct |
39 ms |
47672 KB |
Output is correct |
| 6 |
Correct |
42 ms |
47600 KB |
Output is correct |
| 7 |
Correct |
29 ms |
47688 KB |
Output is correct |
| 8 |
Correct |
4872 ms |
50244 KB |
Output is correct |
| 9 |
Correct |
4251 ms |
50288 KB |
Output is correct |
