1486D - Max Median - CodeForces Solution

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+10;
const int mod=1e9+7;
int n,m,b[N],c[N];
struct node{
	int l,r,val,lazy;
}a[N<<2];
void build(int p,int l,int r){
	a[p].l=l;a[p].r=r;a[p].lazy=-1;a[p].val=0x3f3f3f3f;
	if(l==r)return;
	int mid=l+r>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void pushdown(int p){
	if(a[p].l!=a[p].r){
		int mid=a[p].l+a[p].r>>1;
		a[p*2].val=a[p].lazy*(mid-a[p].l+1);
		a[p*2+1].val=a[p].lazy*(a[p].r-mid);
		a[p*2].lazy=a[p*2+1].lazy=a[p].lazy;
	}
	a[p].lazy=-1;
}
void change(int p,int l,int r,int x){
	if(l<=a[p].l&&r>=a[p].r){
		a[p].val=x*(a[p].r-a[p].l+1);
		a[p].lazy=x;
		return;
	}
	if(a[p].lazy!=-1)pushdown(p);
	int mid=a[p].l+a[p].r>>1;
	if(l<=mid)change(p*2,l,r,x);
	if(r>mid)change(p*2+1,l,r,x);
	a[p].val=a[p*2].val+a[p*2+1].val;
}
int query(int p,int x){
	if(a[p].l==a[p].r)return a[p].val;
	if(a[p].lazy!=-1)pushdown(p);
	int mid=a[p].l+a[p].r>>1;
	if(x<=mid)return query(p*2,x);
	else return query(p*2+1,x);
}
int check(int x){
	for(int i=1;i<=n;i++){
		if(b[i]>=x)c[i]=1;
		else c[i]=-1;
	}
	for(int i=1;i<=n;i++)c[i]+=c[i-1];
	build(1,1,n*2+10);
	int mx=0;
	for(int i=n;i>=0;i--)change(1,c[i]+1+n,n*2,i);
	for(int i=1;i<=n;i++){
		int r=i,l=query(1,c[i]+n);
		mx=max(mx,r-l);
	}
	return mx>=m;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>b[i];
	int l=1,r=n;
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	cout<<l<<'\n';
}