Submission #1232198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232198		ansori	Radio Towers (IOI22_towers)	C++20	11 / 100	4051 ms	10268 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
#define se second
#define fi first
using namespace std;
const int N = 1e5 + 2; 
int d , n;
vector<int> h;
bool fr;
int sp[N][19] , lg[N] , spr[N][19];
vector<int> gg;
pair<int , int> p[N];
int get(int l , int r){
	if(r < l) return -1; 
	int b = lg[r - l + 1];
	return max(sp[l][b] , sp[r - (1 << b) + 1][b]);
}
int getr(int l , int r){
	if(r < l) return 1e9; 
	int b = lg[r - l + 1];
	return min(spr[l][b] , spr[r - (1 << b) + 1][b]);
}
void init(int N, std::vector<int> H) {
	for(auto to : H)  h.push_back(to);
	n = N; 
	fr = false;
	lg[0] = -1;
	for(int i = 1;i <= n; ++ i){
		lg[i] = lg[i / 2] + 1;
		sp[i - 1][0] = h[i - 1];
	}
	for(int i = 1;i <= 18; ++ i){
		int b = (1 << (i - 1));
		for(int j = 0;j < n; ++ j){
			if(j + b * 2 > n) break;
			sp[j][i] = max(sp[j][i - 1] , sp[j + b][i - 1]);
		}
	}
}

int max_towers(int L, int R, int D) {
	d = D;
	vector<pair<pair<int , int> , int>> v;
	set<pair<int , int>> st;
	for(int i = L;i <= R; ++ i){
		bool ok = true;
	   	int l = L - 1;
	   	int r = i;
	   	while(l + 1 < r){
	   		int mid = (l + r) / 2;
	   		if(get(mid , i) >= h[i] + d) l = mid;
	   		else r = mid;
	   	}
	   	p[i].fi = l;
	   	l = i;
	   	r = R + 1;
	   	while(l + 1 < r){
	   		int mid = (l + r) / 2;
	   		if(get(i , mid) >= h[i] + d) r = mid;
	   		else l = mid;
	   	}
	   	p[i].se = r;
	}
	for(int i = L;i <= R; ++ i){
		bool ok = true;
		for(int j = L;j <= R; ++ j){
			if((p[i].fi <= p[j].fi and p[i].se >= p[j].se) and (p[i].fi != p[j].fi or p[i].se != p[j].se)) ok = false;
		}
		if(ok){
			st.insert({p[i].fi , p[i].se});
		}
	}

	fr = true;
	return st.size();
}

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