Submission #1130730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130730		StefanSebez	Radio Towers (IOI22_towers)	C++20	100 / 100	1671 ms	42388 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,lg=17;
const ll inf=2e9+50;
int n,a[N];
int Maks[N][lg+1],LOG[N+50];
int MAKS(int l,int r){if(l>r)return 0;int i=LOG[r-l+1];return max(Maks[l][i],Maks[r-(1<<i)+1][i]);}
int Lm[N],Rm[N];
vector<pair<ll,ll>>nesto;
int root[N];
struct PersistentSegTree{
	int nc,lc[N*(lg+5)],rc[N*(lg+5)],sum[N*(lg+5)];
	void Update(int &c,int c1,int ss,int se,int qind,int x){
		c=++nc;lc[c]=lc[c1],rc[c]=rc[c1],sum[c]=sum[c1];
		if(ss==se){sum[c]=x;return;}
		int mid=ss+se>>1;
		if(qind<=mid) Update(lc[c],lc[c1],ss,mid,qind,x);
		else Update(rc[c],rc[c1],mid+1,se,qind,x);
		sum[c]=sum[lc[c]]+sum[rc[c]];
	}
	int Get(int c,int ss,int se,int qs,int qe){
		if(qs>qe||qe<ss||se<qs)return 0;
		if(qs<=ss&&se<=qe)return sum[c];
		int mid=ss+se>>1;return Get(lc[c],ss,mid,qs,qe)+Get(rc[c],mid+1,se,qs,qe);
	}
}PST;
struct Node{ll maks,mn,ind,val1,val2;};
Node Merge(Node a,Node b){
	Node c;
	c.maks=max(a.maks,b.maks);
	c.mn=min(a.mn,b.mn);
	if(a.mn<=b.mn) c.ind=a.ind;
	else c.ind=b.ind;
	c.val1=max({a.val1,b.val1,b.maks-a.mn});
	c.val2=max({a.val2,b.val2,a.maks-b.mn});
	return c;
}
struct SegTree1{
	int root,nc,lc[2*N],rc[2*N];Node node[2*N];
	void Build(int &c,int ss,int se){
		c=++nc;
		if(ss==se){node[c]={a[ss],a[ss],ss,0,0};return;}
		int mid=ss+se>>1;
		Build(lc[c],ss,mid),Build(rc[c],mid+1,se);
		node[c]=Merge(node[lc[c]],node[rc[c]]);
	}
	Node Get(int c,int ss,int se,int qs,int qe){
		if(qs>qe||qe<ss||se<qs)return {0,inf,0,0};
		if(qs<=ss&&se<=qe)return node[c];
		int mid=ss+se>>1;return Merge(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
	}
}ST1;
void init(int N, std::vector<int> H){
	n=N;
	for(int i=1;i<=n;i++) a[i]=H[i-1];
	for(int i=1,e=1,ct=-1;i<=N;i++){if(i==e)e<<=1,ct++;LOG[i]=ct;}
	for(int i=1;i<=n;i++) Maks[i][0]=a[i];
	for(int j=0;j<lg;j++) for(int i=1;i<=n;i++) if(i+(1<<j)<=n) Maks[i][j+1]=max(Maks[i][j],Maks[i+(1<<j)][j]);
	vector<int>mono;
	for(int i=1;i<=n;i++){
		Lm[i]=0,Rm[i]=n+1;
		while(!mono.empty()&&a[mono.back()]>a[i]){
			Rm[mono.back()]=i;
			mono.pop_back();
		}
		if(!mono.empty()) Lm[i]=mono.back();
		mono.pb(i);
	}
	for(int i=1;i<=n;i++){
		ll x=inf,y=inf;
		if(Lm[i]>0) x=MAKS(Lm[i]+1,i-1);
		if(Rm[i]<=n) y=MAKS(i+1,Rm[i]-1);
		nesto.pb({min(x,y)-a[i],i});
	}
	sort(nesto.begin(),nesto.end());
	reverse(nesto.begin(),nesto.end());
	for(int i=0;i<nesto.size();i++) PST.Update(root[i+1],root[i],1,n,nesto[i].se,1);
	ST1.Build(ST1.root,1,n);
}
int max_towers(int L, int R, int D){
	L++,R++;
	int l=0,r=n-1,ind,rt;
	while(l<=r){
		int mid=l+r>>1;
		if(nesto[mid].fi>=D){ind=mid;l=mid+1;}
		else r=mid-1;
	}
	rt=root[ind+1];
	int res=PST.Get(rt,1,n,L,R);
	if(res==0) res=1;
	l=L,r=R;
	int levo=ST1.Get(ST1.root,1,n,L,R).ind;
	while(l<=r){
		int mid=l+r>>1;
		int x=PST.Get(rt,1,n,L,mid);
		if(x>0){levo=mid;r=mid-1;}
		else l=mid+1;
	}
	l=L,r=levo-1;
	int L1=L-1;
	while(l<=r){
		int mid=l+r>>1;
		ll x=MAKS(mid,levo-1);
		if(x-D>=a[levo]){L1=mid;l=mid+1;}
		else r=mid-1;
	}
	if(ST1.Get(ST1.root,1,n,L,L1).val1>=D) res++;

	l=L,r=R;
	int desno=ST1.Get(ST1.root,1,n,L,R).ind;
	while(l<=r){
		int mid=l+r>>1;
		int x=PST.Get(rt,1,n,mid,R);
		if(x>0){desno=mid;l=mid+1;}
		else r=mid-1;
	}
	l=desno+1,r=R;
	int R1=R+1;
	while(l<=r){
		int mid=l+r>>1;
		ll x=MAKS(desno+1,mid);
		if(x-D>=a[desno]){R1=mid;r=mid-1;}
		else l=mid+1;
	}
	if(ST1.Get(ST1.root,1,n,R1,R).val2>=D) res++;
	return res;
}

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23