#include"holiday.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define emb emplace_back #define all(x) x.begin(),x.end() #define sp << " " << #define inf 1e9 typedef tuple<int,int,int,int> iiii; struct Node{ int64_t sum; int sz,l,r; Node(){sz=sum=l=r=0;} Node(int ll,int rr){sz=sum=0;l=ll;r=rr;} }; vector<Node> st; vector<int> root; vector<int> zort; int addNode(int l,int r){ st.emplace_back(l,r); st.back().sz=st[l].sz+st[r].sz; st.back().sum=st[l].sum+st[r].sum; return st.size()-1; } int update(int node,int l,int r,int qx){ if(l==r){ if(!node) node=addNode(0,0); st[node].sz++; st[node].sum+=zort[qx]; return node; } int mid=(l+r)/2; if(qx<=mid) return addNode(update(st[node].l,l,mid,qx),st[node].r); else return addNode(st[node].l,update(st[node].r,mid+1,r,qx)); } int64_t query(int nodeL,int nodeR,int l,int r,int qk){ if(l==r) return 1LL*qk*zort[l]; int t=st[st[nodeR].r].sz-st[st[nodeL].r].sz; int mid=(l+r)/2; if(qk>=t) return query(st[nodeL].l,st[nodeR].l,l,mid,qk-t)+(st[st[nodeR].r].sum-st[st[nodeL].r].sum); else return query(st[nodeL].r,st[nodeR].r,mid+1,r,qk); } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { for(int i=0;i<n;i++) zort.pb(attraction[i]); sort(all(zort)); zort.resize(unique(all(zort))-zort.begin()); root.pb(addNode(0,0)); for(int i=0;i<n;i++){ int j=lower_bound(all(zort),attraction[i])-zort.begin(); root.pb(update(root[i],0,zort.size()-1,j)); } //~ cout << "yuppi" << endl; int64_t ans=0; queue<iiii> q; q.emplace(0,start,start,n-1); while(!q.empty()){ int optl,optr,l,r; tie(optl,optr,l,r)=q.front(); q.pop(); //~ cout << optl sp optr sp l sp r << endl; int mid=(l+r)/2; pair<int64_t,int> opt={0,start}; for(int i=optl;i<=optr;i++){ int t=(mid-i)+min(start-i,mid-start); if(t<=d){ int64_t val=query(root[i],root[mid+1],0,zort.size()-1,min(d-t,mid-i+1)); opt=max(opt,make_pair(val,i)); } } ans=max(ans,opt.first); if(l<r){ q.emplace(optl,opt.second,l,mid-1); q.emplace(opt.second,optr,mid+1,r); } } return ans; }