제출 #835035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835035		ttamx	송신탑 (IOI22_towers)	C++17	23 / 100	4086 ms	10336 KiB

towers

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

using namespace std;

const int N=1e5+5;
const int LG=17;

int n;
int h[N],sp[LG][N];

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

void init(int N,vector<int> H){
	n=N;
	for(int i=1;i<=n;i++)sp[0][i]=h[i]=H[i-1];
	for(int i=1;i<LG;i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1<<(i-1))]);
		}
	}
}

int max_towers(int L,int R,int D){
	L++,R++;
	vector<pair<int,int>> vec;
	for(int i=L;i<=R;i++)vec.emplace_back(h[i],i);
	sort(vec.begin(),vec.end());
	set<int> ans;
	auto lb=[&](int id){
		int l=L-1,r=id-1;
		while(l<r){
			int m=(l+r+1)/2;
			if(rmq(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(rmq(id,m)>=h[id]+D)r=m;
			else l=m+1;
		}
		return l;
	};
	for(auto [hei,id]:vec){
		int l=lb(id),r=ub(id);
		auto it=ans.lower_bound(l);
		if(it==ans.end()||*it>r)ans.emplace(id);
	}
	return ans.size();
}

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