#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define sz(v) ((int)v.size())
#define pb push_back
#define pry cout << "YES\n"
#define prn cout << "NO\n"
#define endl '\n'
#define fst first
#define scn second
using pll = priority_queue<ll>;
int *a;
int s, n;
const int N = 1e5;
const int D = 2 * N + (N>>1);
int sind[N+2];
int sval[N+2];
int trk[4*N];
ll tr[4*N];
ll r1[D+2];
ll r2[D+2];
ll l1[D+2];
ll l2[D+2];
void
clear()
{
for (int i = 0; i < 4*N; ++i) { tr[i] = 0; trk[i] = 0; }
return;
}
ll
query(int i, int l, int r, int k)
{
int mid = (l+r)>>1;
if (k < 1) return 0;
if (l == k) return tr[i];
if (k >= trk[i]) return tr[i];
return query(i<<1,l,mid,k) + query(i<<1|1,mid+1,r,k-trk[i<<1]);
}
ll
query(int k)
{
return query(1,0,n-1,k);
}
void
upd(int i, int l, int r, int t, int v1, int v2)
{
int mid = (l+r)>>1;
if (l == r) {
if (t != l) return;
tr[i] = v1;
trk[i] = v2;
return;
}
if (l > t || r < t) return;
upd(i<<1,l,mid,t,v1,v2);
upd(i<<1|1,mid+1,r,t,v1,v2);
tr[i] = tr[i<<1] + tr[i<<1|1];
trk[i] = trk[i<<1] + trk[i<<1|1];
return;
}
void
upd(int x, int v1, int v2)
{
x = sind[x];
upd(1,0,n-1,x,v1,v2);
return;
}
void
computer1(int l, int r, int optl, int optr)
{
int mid = (l+r)>>1;
ll nv, best = -inf;
int opt = optl;
if (l > r) return;
for (int i = optl; i <= optr; ++i) {
if (abs(i-s) > mid) break;
upd(i,a[i],1);
nv = query(mid-abs(i-s));
if (nv > best) {
best = nv;
opt = i;
}
}
r1[mid] = best;
for (int i = optl; i <= optr; ++i) upd(i,0,0);
computer1(l,mid-1,optl,opt);
for (int i = optl; i <= opt; ++i) upd(i,a[i],1);
computer1(mid+1,r,opt,optr);
return;
}
void
computer2(int l, int r, int optl, int optr)
{
int mid = (l+r)>>1;
ll nv, best = -inf;
int opt = optl;
if (l > r) return;
for (int i = optl; i <= optr; ++i) {
if (2*abs(i-s) > mid) break;
upd(i,a[i],1);
nv = query(mid-2*abs(i-s));
if (nv > best) {
best = nv;
opt = i;
}
}
r2[mid] = best;
for (int i = optl; i <= optr; ++i) upd(i,0,0);
computer2(l,mid-1,optl,opt);
for (int i = optl; i <= opt; ++i) upd(i,a[i],1);
computer2(mid+1,r,opt,optr);
return;
}
void
computel1(int l, int r, int optl, int optr)
{
int mid = (l+r)>>1;
ll nv, best = -inf;
int opt = optl;
if (l > r) return;
for (int i = optl; i >= optr; --i) {
if (abs(i-s) > mid) break;
upd(i,a[i],1);
nv = query(mid-abs(i-s));
if (nv > best) {
best = nv;
opt = i;
}
}
l1[mid] = best;
for (int i = optl; i >= optr; --i) upd(i,0,0);
computel1(l,mid-1,optl,opt);
for (int i = optl; i >= opt; --i) upd(i,a[i],1);
computel1(mid+1,r,opt,optr);
return;
}
void
computel2(int l, int r, int optl, int optr)
{
int mid = (l+r)>>1;
ll nv, best = -inf;
int opt = optl;
if (l > r) return;
for (int i = optl; i >= optr; --i) {
if (2*abs(i-s) > mid) break;
upd(i,a[i],1);
nv = query(mid-2*abs(i-s));
if (nv > best) {
best = nv;
opt = i;
}
}
l2[mid] = best;
for (int i = optl; i >= optr; --i) upd(i,0,0);
computel2(l,mid-1,optl,opt);
for (int i = optl; i >= opt; --i) upd(i,a[i],1);
computel2(mid+1,r,opt,optr);
return;
}
ll
findMaxAttraction(int _n, int _s, int d, int _a[])
{
vector<pair<int,int>> _v;
a = _a;
s = _s;
n = _n;
for (int i = 0; i < n; ++i) _v.pb({_a[i],i});
sort(_v.begin(), _v.end());
reverse(_v.begin(), _v.end());
for (int i = 0; i < n; ++i) {
sind[_v[i].scn] = i;
sval[i] = _v[i].fst;
}
clear();
computer1(0,d,s,n-1);
clear();
computer2(0,d,s,n-1);
if (s) {
clear();
computel1(0,d,s-1,0);
clear();
computel2(0,d,s-1,0);
}
ll ans = max(l1[d],r1[d]);
for (int i = 0; i < d+1; ++i) {
ans = max(ans, l1[i] + r2[d-i]);
ans = max(ans, r1[i] + l2[d-i]);
}
return ans;
}
#ifdef ONPC
void
solve()
{
int n, s, d;
cin >> n >> s >> d;
int _a[n];
for (int i = 0; i < n; ++i)
cin >> _a[i];
cout << findMaxAttraction(n,s,d,_a) << endl;
}
int32_t
main(int argc, char **argv)
{
if (argc >= 2) {
freopen(argv[1], "r", stdin);
} else
ios_base::sync_with_stdio(0);cin.tie(0);
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5432 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5436 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5332 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5332 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1702 ms |
10504 KB |
Output is correct |
| 2 |
Correct |
1371 ms |
10500 KB |
Output is correct |
| 3 |
Correct |
1727 ms |
10420 KB |
Output is correct |
| 4 |
Correct |
1370 ms |
10484 KB |
Output is correct |
| 5 |
Correct |
1659 ms |
9244 KB |
Output is correct |
| 6 |
Correct |
656 ms |
8880 KB |
Output is correct |
| 7 |
Correct |
936 ms |
7796 KB |
Output is correct |
| 8 |
Correct |
1044 ms |
8000 KB |
Output is correct |
| 9 |
Correct |
544 ms |
9568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
5716 KB |
Output is correct |
| 2 |
Correct |
38 ms |
5668 KB |
Output is correct |
| 3 |
Correct |
39 ms |
5668 KB |
Output is correct |
| 4 |
Correct |
32 ms |
5588 KB |
Output is correct |
| 5 |
Correct |
31 ms |
5592 KB |
Output is correct |
| 6 |
Correct |
9 ms |
5448 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5460 KB |
Output is correct |
| 8 |
Correct |
8 ms |
5436 KB |
Output is correct |
| 9 |
Correct |
9 ms |
5460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2013 ms |
15704 KB |
Output is correct |
| 2 |
Correct |
1928 ms |
11932 KB |
Output is correct |
| 3 |
Correct |
378 ms |
6920 KB |
Output is correct |
| 4 |
Correct |
22 ms |
5448 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5432 KB |
Output is correct |
| 6 |
Correct |
9 ms |
5460 KB |
Output is correct |
| 7 |
Correct |
10 ms |
5588 KB |
Output is correct |
| 8 |
Correct |
1512 ms |
9612 KB |
Output is correct |
| 9 |
Correct |
1511 ms |
9524 KB |
Output is correct |
