#include<bits/stdc++.h>
using namespace std;
#define vll vector<ll>
typedef long long ll;
const ll inf=1e18;
const ll mxN=1e5+5;
unordered_map<ll, ll> idx;
unordered_map<ll, ll> vl;
ll ans;
ll s;
ll d;
ll n;
ll val[mxN];
ll de[mxN];
struct segtree1{
vll tree;
vll lazy;
ll treelen;
void init(ll s){
tree.clear();
lazy.clear();
treelen=s+1;
while(__builtin_popcountll(treelen)!=1){
treelen++;
}
tree.resize(2*treelen);
lazy.resize(2*treelen);
}
void update(ll idx, ll low, ll high, ll qlow, ll qhigh, ll val){
if(low>high) return;
if(lazy[idx]!=0){
tree[idx]+=lazy[idx];
if(low!=high){
lazy[2*idx]+=lazy[idx];
lazy[2*idx+1]+=lazy[idx];
}
lazy[idx]=0;
}
if(low>=qlow && high<=qhigh){
tree[idx]+=val;
if(low!=high){
lazy[2*idx]+=val;
lazy[2*idx+1]+=val;
}
return;
}
if(low>qhigh || high<qlow){
return;
}
ll mid=(low+high)/2;
update(2*idx, low, mid, qlow, qhigh, val);
update(2*idx+1, mid+1, high, qlow, qhigh, val);
tree[idx]=max(tree[2*idx], tree[2*idx+1]);
}
ll qry(ll idx, ll low, ll high, ll val){
if(lazy[idx]!=0){
tree[idx]+=lazy[idx];
if(low!=high){
lazy[2*idx]+=lazy[idx];
lazy[2*idx+1]+=lazy[idx];
}
lazy[idx]=0;
}
if(tree[idx]<val){
return -inf;
}
if(low==high){
return low;
}
ll mid=(low+high)/2;
if(tree[2*idx+1]+lazy[2*idx+1]>=val){
return qry(2*idx+1, mid+1, high, val);
}
else{
return qry(2*idx, low, mid, val);
}
}
ll getval(ll idx, ll low, ll high, ll qlow, ll qhigh){
if(low>high) return 0;
if(lazy[idx]!=0){
tree[idx]+=lazy[idx];
if(low!=high){
lazy[2*idx]+=lazy[idx];
lazy[2*idx+1]+=lazy[idx];
}
lazy[idx]=0;
}
if(low>=qlow && high<=qhigh){
return tree[idx];
}
if(low>qhigh || high<qlow){
return 0;
}
ll mid=(low+high)/2;
return max(getval(2*idx, low, mid, qlow, qhigh)
, getval(2*idx+1, mid+1, high, qlow, qhigh));
}
};
struct BIT{
vll tree;
ll siz;
void init(ll s){
siz=s+1;
tree.clear();
tree.resize(siz);
}
void update(ll idx, ll val){
idx++;
for(;idx<siz;idx+=(idx&-idx)){
tree[idx]+=val;
}
}
ll getpre(ll idx){
idx++;
ll re=0;
for(;idx>0;idx-=(idx&-idx)){
re+=tree[idx];
}
return re;
}
ll getsum(ll a, ll b){
if(a==0) return getpre(b);
return getpre(b)-getpre(a-1);
}
};
segtree1 seg;
BIT bit;
ll p1;
ll qrylef(ll lef){
ll id=seg.qry(1, 0, seg.treelen-1, lef);
if(id==-inf){
return bit.getsum(0, n-1);
}
else{
ll re=bit.getsum(id, n-1);
if(seg.getval(1, 0, seg.treelen-1, id, id)>lef){
re-=bit.getsum(id, id)*(seg.getval(1, 0, seg.treelen-1, id, id)-lef);
}
return re;
}
}
void divi(ll low, ll high, ll qlow, ll qhigh, ll flag){
if(low>high) return;
ll mid=(low+high)/2;
while(p1>mid){
p1--;
seg.update(1, 0, seg.treelen-1, 0, idx[val[p1]], 1);
bit.update(idx[val[p1]], val[p1]);
}
while(p1<mid){
seg.update(1, 0, seg.treelen-1, 0, idx[val[p1]], -1);
bit.update(idx[val[p1]], -val[p1]);
p1++;
}
if(flag==1){
ll cur=-inf;
ll lef=d-(qlow-mid)-(qlow-s);
cur=max(cur, qrylef(lef));
ll op=qlow;
for(ll i=qlow+1;i<=qhigh;i++){
seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], 1);
bit.update(idx[val[i]], val[i]);
lef=d-(i-mid)-(i-s);
if(lef<=0) break;
if(qrylef(lef)>cur){
cur=qrylef(lef);
op=i;
}
}
ans=max(ans, cur);
for(ll i=qhigh;i>op;i--){
lef=d-(i-mid)-(i-s);
if(lef<=0) continue;
seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], -1);
bit.update(idx[val[i]], -val[i]);
}
divi(low, mid-1, qlow, op, 0);
divi(mid+1, high, op, qhigh, 1);
for(ll i=op;i>qlow;i--){
seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], -1);
bit.update(idx[val[i]], -val[i]);
}
}
else{
ll cur=-inf;
ll lef=d-(qhigh-mid)-(qlow-s);
ll id=seg.qry(1, 0, seg.treelen-1, lef);
if(id==-inf){
cur=max(cur, bit.getsum(0, n-1));
}
else{
cur=max(cur, bit.getsum(id, n-1));
}
ll op=qhigh;
for(ll i=qhigh-1;i>=qlow;i--){
seg.update(1, 0, seg.treelen-1, 0, idx[val[i+1]], -1);
bit.update(idx[val[i+1]], -val[i]);
lef=d-(i-mid)-(i-s);
if(lef<=0) continue;
if(qrylef(lef)>=cur){
cur=qrylef(lef);
op=i;
}
}
ans=max(ans, cur);
for(ll i=qlow+1;i<=op;i++){
seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], 1);
bit.update(idx[val[i]], val[i]);
}
divi(low, mid-1, qlow, op, 0);
divi(mid+1, high, op, qhigh, 1);
for(ll i=op+1;i<=qhigh;i++){
lef=d-(i-mid)-(i-s);
if(lef<=0) continue;
seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], 1);
bit.update(idx[val[i]], val[i]);
}
}
}
void divi2(ll low, ll high, ll qlow, ll qhigh, ll flag){
if(low>high) return;
ll mid=(low+high)/2;
while(p1>mid){
seg.update(1, 0, seg.treelen-1, 0, idx[val[p1]], -1);
bit.update(idx[val[p1]], -val[p1]);
p1--;
}
while(p1<mid){
p1++;
seg.update(1, 0, seg.treelen-1, 0, idx[val[p1]], 1);
bit.update(idx[val[p1]], val[p1]);
}
if(flag==1){
ll cur=-inf;
ll lef=d+(qlow-mid)+(qlow-s);
if(qrylef(lef)>cur){
cur=qrylef(lef);
}
ll op=qlow;
for(ll i=qlow+1;i<=qhigh;i++){
seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], -1);
bit.update(idx[val[i]], -val[i]);
lef=d+(i-mid)+(i-s);
if(lef<=0) break;
if(qrylef(lef)>=cur){
cur=qrylef(lef);
op=i;
}
}
ans=max(ans, cur);
de[mid]=cur;
for(ll i=qhigh;i>op;i--){
seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], 1);
bit.update(idx[val[i]], val[i]);
}
divi2(low, mid-1, qlow, op, 0);
divi2(mid+1, high, op, qhigh, 1);
for(ll i=op;i>qlow;i--){
lef=d+(i-mid)+(i-s);
if(lef<=0) continue;
seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], 1);
bit.update(idx[val[i]], val[i]);
}
}
else{
ll cur=-inf;
ll lef=d+(qhigh-mid)+(qhigh-s);
ll id=seg.qry(1, 0, seg.treelen-1, lef);
if(id==-inf){
cur=max(cur, bit.getsum(0, n-1));
}
else{
cur=max(cur, bit.getsum(id, n-1));
}
ll op=qhigh;
for(ll i=qhigh-1;i>=qlow;i--){
seg.update(1, 0, seg.treelen-1, 0, idx[val[i+1]], 1);
bit.update(idx[val[i+1]], val[i]);
lef=d+(i-mid)+(i-s);
if(lef<=0) continue;
if(qrylef(lef)>cur){
cur=qrylef(lef);
op=i;
}
}
ans=max(ans, cur);
de[mid]=cur;
for(ll i=qlow+1;i<=op;i++){
lef=d+(i-mid)+(i-s);
if(lef<=0) continue;
seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], -1);
bit.update(idx[val[i]], -val[i]);
}
divi2(low, mid-1, qlow, op, 0);
divi2(mid+1, high, op, qhigh, 1);
for(ll i=op+1;i<=qhigh;i++){
seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], -1);
bit.update(idx[val[i]], -val[i]);
}
}
}
ll findMaxAttraction(int tn, int st, int td, int a[]){
if(td==0) return 0;
s=st;
d=td;
n=tn;
ans=a[s];
seg.init(n);
bit.init(n);
set<ll> cor;
for(ll i=0;i<n;i++){
cor.insert(a[i]);
val[i]=a[i];
}
ll cnt=0;
for(auto it:cor){
idx[it]=cnt;
vl[cnt]=it;
cnt++;
}
p1=s;
seg.update(1, 0, seg.treelen-1, 0, idx[val[s]], 1);
bit.update(idx[val[s]], val[s]);
divi(0, s-1, s, n-1, 1);
while(p1<s){
seg.update(1, 0, seg.treelen-1, 0, idx[val[p1]], -1);
bit.update(idx[val[p1]], -val[p1]);
p1++;
}
divi2(s+1, n-1, 0, s, 0);
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
182 ms |
7056 KB |
Output is correct |
| 2 |
Correct |
162 ms |
7248 KB |
Output is correct |
| 3 |
Correct |
151 ms |
7044 KB |
Output is correct |
| 4 |
Correct |
157 ms |
7068 KB |
Output is correct |
| 5 |
Incorrect |
216 ms |
7092 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
1372 KB |
Output is correct |
| 2 |
Correct |
4 ms |
860 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1372 KB |
Output is correct |
| 4 |
Incorrect |
20 ms |
1368 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
161 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
233 ms |
20796 KB |
Output is correct |
| 3 |
Incorrect |
351 ms |
9924 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
