Submission #1232099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232099		ansori	Radio Towers (IOI22_towers)	C++20	0 / 100	4086 ms	18168 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;
	for(int i = L;i <= R; ++ i){
	   		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;
	   			// 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});
				}
	   		}
	}
	fr = true;
	return v.size();
}

• 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