Submission #835084

#	Time	Username	Problem	Language	Result	Execution time	Memory
835084		ttamx	송신탑 (IOI22_towers)	C++17	100 / 100	1216 ms	118284 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> p2;

const int N=1e5+5;
const int K=1<<18;
const int LG=17;
const int inf=2e9;

int n;
int h[N],spmx[LG][N],spmn[LG][N],spid[LG][N];
vector<pair<int,int>> vec;

struct persist{
	struct info{
		int mn,mx,val;
		info():mn(inf),mx(-inf),val(0){}
		info(int x):mn(x),mx(x),val(1){}
		friend info operator+(info a,info b){
			info c;
			c.mn=min(a.mn,b.mn);
			c.mx=max(a.mx,b.mx);
			c.val=a.val+b.val;
			return c;
		}
	};
	struct node;
	typedef node* pnode;
	struct node{
		info val;
		pnode l,r;
		node():val(),l(nullptr),r(nullptr){}
	};
	pnode rt[N];
	void build(int l,int r,pnode &t){
		t=new node();
		if(l==r)return;
		int m=(l+r)/2;
		build(l,m,t->l);
		build(m+1,r,t->r);
	}
	void build(int t){
		build(1,n,rt[t]);
	}
	void update(int l,int r,pnode &t,pnode k,int x){
		t=new node(*k);
		t->val=t->val+info(x);
		if(l==r)return;
		int m=(l+r)/2;
		if(x<=m)update(l,m,t->l,k->l,x);
		else update(m+1,r,t->r,k->r,x);
	}
	void update(int k,int t,int x){
		update(1,n,rt[t],rt[k],x);
	}
	info query(int l,int r,pnode t,int x,int y){
		if(y<l||r<x)return info();
		if(x<=l&&r<=y)return t->val;
		int m=(l+r)/2;
		return query(l,m,t->l,x,y)+query(m+1,r,t->r,x,y);
	}
	info query(int t,int x,int y){
		return query(1,n,rt[t],x,y);
	}
}pst;

struct segtree{
	struct node{
		int mn,mx,vl,vr;
		node(int x=0):mn(x),mx(x),vl(0),vr(0){}
		friend node operator+(node a,node b){
			node c;
			c.mn=min(a.mn,b.mn);
			c.mx=max(a.mx,b.mx);
			c.vl=max({a.vl,b.vl,b.mx-a.mn});
			c.vr=max({a.vr,b.vr,a.mx-b.mn});
			return c;
		}
	}t[K];
	void build(int l,int r,int i){
		if(l==r)return void(t[i]=node(h[l]));
		int m=(l+r)/2;
		build(l,m,i*2);
		build(m+1,r,i*2+1);
		t[i]=t[i*2]+t[i*2+1];
	}
	void build(){
		build(1,n,1);
	}
	node query(int l,int r,int i,int x,int y){
		if(x<=l&&r<=y)return t[i];
		int m=(l+r)/2;
		if(y<=m)return query(l,m,i*2,x,y);
		if(m<x)return query(m+1,r,i*2+1,x,y);
		return query(l,m,i*2,x,y)+query(m+1,r,i*2+1,x,y);
	}
	node query(int x,int y){
		return query(1,n,1,x,y);
	}
}s;

int rmxq(int l,int r){
	int k=31-__builtin_clz(r-l+1);
	return max(spmx[k][l],spmx[k][r-(1<<k)+1]);
}

int rmnq(int l,int r){
	int k=31-__builtin_clz(r-l+1);
	return min(spmn[k][l],spmn[k][r-(1<<k)+1]);
}

int rmidq(int l,int r){
	int k=31-__builtin_clz(r-l+1);
	return spmn[k][l]<spmn[k][r-(1<<k)+1]?spid[k][l]:spid[k][r-(1<<k)+1];
}

void init(int N,vector<int> H){
	n=N;
	for(int i=1;i<=n;i++)h[i]=H[i-1];
	h[0]=h[n+1]=inf;
	for(int i=0;i<=n+1;i++){
		spmx[0][i]=spmn[0][i]=h[i];
		spid[0][i]=i;
	}
	for(int i=1;i<LG;i++){
		for(int j=0;j+(1<<i)-1<=n+1;j++){
			spmx[i][j]=max(spmx[i-1][j],spmx[i-1][j+(1<<(i-1))]);
			spmn[i][j]=min(spmn[i-1][j],spmn[i-1][j+(1<<(i-1))]);
			spid[i][j]=spmn[i-1][j]<spmn[i-1][j+(1<<(i-1))]?spid[i-1][j]:spid[i-1][j+(1<<(i-1))];
		}
	}
	auto lb=[&](int id){
		int l=0,r=id-1;
		while(l<r){
			int m=(l+r+1)/2;
			if(rmnq(m,id)<h[id])l=m;
			else r=m-1;
		}
		return l;
	};
	auto ub=[&](int id){
		int l=id+1,r=n+1;
		while(l<r){
			int m=(l+r)/2;
			if(rmnq(id,m)<h[id])r=m;
			else l=m+1;
		}
		return l;
	};
	for(int i=1;i<=n;i++){
		int l=lb(i),r=ub(i);
		int d=min(rmxq(l,i),rmxq(i,r))-h[i];
		vec.emplace_back(d,i);
	}
	vec.emplace_back(-inf,-1);
	sort(vec.begin(),vec.end());
	pst.build(n+1);
	for(int i=n;i>=1;i--){
		pst.update(i+1,i,vec[i].second);
	}
	s.build();
}

int max_towers(int L,int R,int D){
	L++,R++;
	auto lb=[&](int id){
		int l=L-1,r=id-1;
		while(l<r){
			int m=(l+r+1)/2;
			if(rmxq(m,id)>=h[id]+D)l=m;
			else r=m-1;
		}
		return l;
	};
	auto ub=[&](int id){
		int l=id+1,r=R+1;
		while(l<r){
			int m=(l+r)/2;
			if(rmxq(id,m)>=h[id]+D)r=m;
			else l=m+1;
		}
		return l;
	};
	int ver=lower_bound(vec.begin(),vec.end(),p2(D,0))-vec.begin();
	auto res=pst.query(ver,L,R);
	int l=res.mn,r=res.mx,ans=res.val;
	if(ans==0){
		l=r=rmidq(L,R);
		ans=1;
	}
	l=lb(l),r=ub(r);
	if(L<l&&s.query(L,l).vl>=D)ans++;
	if(r<R&&s.query(r,R).vr>=D)ans++;
	return ans;
}

• 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