PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Segment tree
PROBLEM:
N monsters appear one at a time, the i-th at position P_i.
P is a permutation of [1, N].
You have a bomb with power K, which can be placed at some position x in [1, N] and given a trigger radius R.
0 \le R \le \min(x-1, N-x) must hold however.
The first time a monster appears inside the trigger radius of the bomb, it explodes, killing all monsters within K distance of it.
Your score equals the number of monsters killed plus the trigger radius R.
Find the maximum possible score.
EXPLANATION:
Suppose we fix monster i, appearing at position P_i, to be the one that triggers the bomb.
If we want the bomb center to be x, then this is possible if and only if:
- The trigger radius R is at least |x-P_i|
- No monsters among 1, 2, \ldots, i-1 appear within the trigger interval [x-R, x+R].
Let’s define
to be the smallest distance of one of the first i-1 monsters from position x.
Observe then the trigger radius R must be strictly less than d_{x, i}, otherwise one of these monsters would trigger the bomb.
So, we need |x-P_i| \lt d_{x, i}, otherwise it’s impossible for monster i to be the one that triggers a bomb placed at position x.
On the other hand, as long as |x - P_i| \lt d_{x, i} holds, any trigger radius from |x-P_i| to d_{x,i}-1 is viable.
Further, observe that the number of monsters killed is in fact completely independent of the trigger radius, and depends only on x and i.
So, it’s optimal to make the trigger radius as large as possible - which means choosing R = d_{x, i} - 1.
If we let c_{x, i} denote the number of monsters killed with the center at x and i being the trigger monster, then the optimal score for this configuration is
We’ll process the monsters in ascending order of their appearance time.
While processing monster i, we’ll also try to maintain the value c_{x, i} + d_{x, i} - 1 at index x.
Suppose the first i-1 monsters have been processed, and we’re looking at monster i now.
This monster can be killed from any center that’s within K distance of it, so it contributes 1 to each of their c_{x, i} values.
This corresponds to adding 1 over a range, which a segment tree can handle easily.
The hard part is keeping the d_{x, i} values updated.
To do that, observe that d_{x, i} equals the distance from x to either the closest monster to the left of x or the closest to the right of x.
So, if we define l_{x, i} to be the nearest index \le x that contains a monster from among the first i monsters, and similarly r_{x, i} to be the nearest index \ge x that contains a monster from among the first i, we have
However, we still have the \min() as part of the expression, which is a bit hard to update.
To deal with this, we instead just work with both parts of the expression separately.
That is, for each index x, store both the values (c_{i, x} + x - l_{x, i} - 1) and (c_{i, x} + r_{x, i} - x - 1) in separate arrays.
The earlier range-add-1 update to c_{i,x} now applies to both these arrays.
Along with the new arrays, let’s bring back in the constraint |x-P_i| \lt d_{x, i} into the picture, i.e. an index x is valid if and only if it’s not “too far” away from P_i, when compared to its nearest previously closest monster.
Let’s look at this a bit closer.
For P_i, let L \lt P_i and R \gt P_i be the monsters that are closest to P_i, to its left and right respectively.
Then, note that x \le L and x \ge R are immediately invalid.
Thus, we’re left with the double-open range (L, R).
Let’s look at the left side of this range, (L, P_i].
Define m = \text{midpoint}(L, P_i).
Then, L \lt x \le m are still closer to L than to P_i, so these x are invalid too.
Thus, we further reduce the range to \text{midpoint}(L, P_i) \lt x \le P_i.
Similarly, on the right side we can reduce the range of x we care about to P_i \le x \lt \text{midpoint}(P_i, R).
In particular, observe that all the “valid” values of x still themselves form a range!
Now, note that some prefix of this range of x will have L be the nearest monster, and the remaining suffix will have the nearest monster be R instead.
So, for the appropriate prefix we want to use the (c_{i, x} + x-l_{i,x}-1) values, while for the remaining suffix we want to use the (c_{i,x}+r_{i,x}-x-1) values.
This corresponds to just a range maximum query on each array.
We thus need a data structure that allows for range addition and range maximum queries, which a segment tree with lazy propagation can handle.
Since each monster is processed in \mathcal{O}(\log N) time, this is \mathcal{O}(N\log N) overall.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Tester's code (C++)
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int INF = 1e18;
struct segtree{
int size;
vector<int> operations;
vector<int> values;
//always check for neutral element
int NEUTRAL_ELEMENT = -INF;
int modify_op(int a,int b){
return a+b;
}
int calc_op(int a,int b){
return max(a,b);
}
void apply_mod_op(int &a,int b){
a=modify_op(a,b);
}
void init(int n){
size=1;
while(size<n)size*=2;
operations.assign(2*size,0LL);
values.assign(2*size,0);
}
void build(vector<int> &a,int x,int lx,int rx){
if(rx-lx==1){
if(lx<a.size()){
values[x]=a[lx];
}
return;
}
int m = (lx+rx)/2;
build(a,2*x+1,lx,m);
build(a,2*x+2,m,rx);
values[x]=(values[2*x+1]+values[2*x+2]);
}
void build(vector<int> &a){
build(a,0,0,size);
}
void modify(int l,int r,int v,int x,int lx,int rx){
if(lx>=r || l>=rx)return;
if(lx>=l && rx<=r){
apply_mod_op(operations[x],v);
apply_mod_op(values[x],v);
return;}
int m = (lx+rx)/2;
modify(l,r,v,2*x+1,lx,m);
modify(l,r,v,2*x+2,m,rx);
values[x]=calc_op(values[2*x+1],values[2*x+2]);
apply_mod_op(values[x],operations[x]);
}
void modify(int l,int r,int v){
return modify(l,r,v,0,0,size);
}
int calc(int l,int r,int x,int lx,int rx){
if(lx>=r || l>=rx)return NEUTRAL_ELEMENT;
if(lx>=l && rx<=r){return values[x];}
int m = (lx+rx)/2;
int m1=calc(l,r,2*x+1,lx,m);
int m2=calc(l,r,2*x+2,m,rx);
auto res = calc_op(m1,m2);
apply_mod_op(res,operations[x]);
return res;
}
int calc(int l,int r){
return calc(l,r,0,0,size);
}
};
void solve() {
int n, k; cin >> n >> k;
vector<int> p(n);
for(int i = 0;i < n;i++){
cin >> p[i];
p[i]--;
}
segtree st,st1;
st1.init(n);
st.init(n);
for(int i = 0;i < n;i++){
st1.modify(i,i+1,i);
st.modify(i,i+1,-i);
}
vector<int> l(n,-1);
vector<int> r(n,n);
set<int> s;
for(int i = 0;i < n;i++){
int x = p[i];
s.insert(x);
auto it = s.find(x);
it++;
if(it != s.end()){
r[i] = (*it);
}
it--;
if(it != s.begin()){
it--;
l[i] = (*it);
it++;
}
}
for(int i = 0;i < n;i++)l[i]++,r[i]--;
int ans = 0;
for(int i = 0;i < n;i++){
st.modify(max(p[i]-k,0LL),min(p[i]+k,n-1)+1,1);
st1.modify(max(p[i]-k,0LL),min(p[i]+k,n-1)+1,1);
int mid = (l[i]+r[i])/2;
int cl = (l[i]+p[i]+1)/2,cr = (r[i]+p[i])/2;
int res = 0;
res = max(res,st1.calc(cl,mid+1)-l[i]);
res = max(res,st.calc(mid+1,cr+1)+r[i]);
ans = max(ans,res);
}
cout << ans << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t; cin >> t;
while (t--) {
solve();
}
return 0;
}