Submission #1232085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232085		ansori	Radio Towers (IOI22_towers)	C++20	0 / 100	35 ms	17760 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;
	if(! fr){
		vector<pair<pair<int , int> , int>> v;
	   	for(int i = 0;i < n; ++ i){
	   		int 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 = n;
	   		while(l + 1 < r){
	   			int mid = (l + r) / 2;
	   			// cout << get(i , mid) << ' ';
	   			if(get(i , mid) >= h[i] + d) r = mid;
	   			else l = mid;
	   		}
	   		p[i].se = r;
	   		l = p[i].fi , r = p[i].se;
	   		//cout << l << ' ' << r << '\n';
	   		spr[i][0] = r;
	   		if(v.size() == 0 or i > v.back().fi.se){
	   			v.push_back({{l , r} , i});
	   		}
	   		else{
	   			if(v.back().fi.fi >= l and v.back().fi.se <= r){
	   				continue ;	
	   			}
	   			else{
	   				v.pop_back();
	   				v.push_back({{l , r} , i});
				}
	   		}
	   	}
		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;
				spr[j][i] = min(spr[j][i - 1] , spr[j + b][i - 1]);
			}
		}
	   	for(auto to : v){
	   		cout << to.fi.fi << ' ' << to.fi.se << '\n';
	   		gg.push_back(to.se);
	   	}
	   	fr = true;
   	}
   	int l1 , r1;
   	int l = -1;
   	int r = gg.size();
	while(l + 1 < r){
		int mid = (l + r) / 2;
		if(gg[mid] < L) l = mid;
		else r = mid;
	}
	l1 = r;
	l = -1;
	r = gg.size();
	while(l + 1 < r){
		int mid = (l + r) / 2;
		if(gg[mid] <= R) l = mid;
		else r = mid;
	}
	r1 = l;
	//cout << l1 << ' ' << r1 << ' ';
	if(l1 > r1) return 1;
	int f = p[gg[l1]].fi - 1 , answ = r1 - l1 + 1;
	if(f >= L){
		//cout << getr(L , f) << ' ';
		if(getr(L , f) < gg[l1]) answ ++;
	}
	return answ;
}

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