#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int,k>
template<class A,class B> void cmx(A& x, B y) {x=max<A>(x,y);}
template<class A,class B> void cmn(A& x, B y) {x=min<A>(x,y);}
typedef pair<int, int> pii;
typedef vector<int> vi;
struct FT {
vector<ll> s;
FT(int n) : s(n) {}
void update(int pos, ll dif) { // a[pos] += dif
for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
}
ll query(int pos) { // sum of values in [0, pos)
ll res = 0;
for (; pos > 0; pos &= pos - 1) res += s[pos-1];
return res;
}
int lower_bound(ll sum) {// min pos st sum of [0, pos] >= sum
// Returns n if no sum is >= sum, or -1 if empty sum is.
if (sum <= 0) return -1;
int pos = 0;
for (int pw = 1 << 25; pw; pw >>= 1) {
if (pos + pw <= sz(s) && s[pos + pw-1] < sum)
pos += pw, sum -= s[pos-1];
}
return pos;
}
};
typedef vector<ll> vll;
vll calc(vi& a, int mul, int len, int base = 0){
int n = sz(a);
vll res(len);
if(!n) return res;
vi vals = a; sort(all(vals),greater<>()); vals.erase(unique(all(vals)),vals.end());
FT cnt(sz(vals)),sum(sz(vals));
auto add = [&](int x, int v){
int pos = lower_bound(all(vals),x,greater<>())-vals.begin();
cnt.update(pos,v);
sum.update(pos,v*x);
};
auto qry = [&](int num){
if(num <= 0) return 0ll;
int pos = cnt.lower_bound(num+1);
ll ext = num-cnt.query(pos);
/*
if(ext < 0){
cerr << "WUT " << num << " " << ext << "\n";
exit(0);
}*/
assert(ext >= 0);
//int cnext = (pos == sz(cnt.s) ? 0 : cnt.query(pos+1)-cnt.query(pos));
ll cur = sum.query(pos);
if(pos < sz(vals)) cur += ext * vals[pos];
return cur;
};
auto rec = [&](auto&& rec, int l, int r, int optl, int optr){
if(l > r) return;
int mid = (l+r)/2; pair<ll,int> ans{-1,0};
for(int i = optl; i <= optr; i++){
int rem = mid-(i+base)*mul;
add(a[i],1);
cmx(ans,pair<ll,int>{qry(rem),-i});
}
assert(ans.FS >= 0);
res[mid] = ans.FS; ans.SD *= -1;
for(int i = optr; i >= ans.SD; i--){
add(a[i],-1);
}
rec(rec,mid+1,r,ans.SD,optr);
for(int i = ans.SD-1; i >= optl; i--){
add(a[i],-1);
}
rec(rec,l,mid-1,optl,ans.SD);
};
rec(rec,0,sz(res)-1,0,n-1);
return res;
}
long long int findMaxAttraction(int n, int s, int d, int attraction[]){
vi a{attraction,attraction+n};
vi rit{a.begin()+s,a.end()};
vi lft{a.begin(),a.begin()+s};
reverse(all(lft));
auto rf = calc(rit,2,3*n);
auto rs = calc(rit,1,3*n);
auto lf = calc(lft,2,3*n,1);
auto ls = calc(lft,1,3*n,1);
ll ans = 0;
rep(i,0,d+1){
cmx(ans,rf[i]+ls[d-i]);
cmx(ans,rs[i]+lf[d-i]);
}
return ans;
}
signed main() {
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
}
Compilation message
/usr/bin/ld: /tmp/ccIxzwBd.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccfFZXwf.o:holiday.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
