Submission #827301

#	Time	Username	Problem	Language	Result	Execution time	Memory
827301		esomer	Radio Towers (IOI22_towers)	C++17	100 / 100	1134 ms	238400 KiB

towers

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

using namespace std;

const int B = 200;

int N, spec, first;
vector<int> H, lw;
vector<pair<int, int>> candidates;
vector<vector<pair<int, int>>> mn, mx;
vector<vector<int>> prefix;

void precalcmx(){
	mx.assign(20, vector<pair<int, int>>(N));
	for(int k = 0; k < 20; k++){
		for(int i = 0; i < N; i++){
			if(k == 0) mx[k][i] = {H[i], i};
			else{
				if(i - (1 << (k-1)) < 0) mx[k][i] = mx[k-1][i];
				else{
					mx[k][i] = max(mx[k-1][i], mx[k-1][i - (1 << (k-1))]);
				}
			}
		}
	}
}

void precalcmn(){
	mn.assign(20, vector<pair<int, int>>(N));
	for(int k = 0; k < 20; k++){
		for(int i = 0; i < N; i++){
			if(k == 0) mn[k][i] = {H[i], i};
			else{
				if(i - (1 << (k-1)) < 0) mn[k][i] = mn[k-1][i];
				else{
					mn[k][i] = min(mn[k-1][i], mn[k-1][i - (1 << (k-1))]);
				}
			}
		}
	}
}

void precalclw(){
	lw.resize(N+1);
	int pw = 0;
	int curr = 2;
	for(int i = 1; i <= N; i++){
		if(i == curr){
			pw++; curr *= 2;
		}
		lw[i] = pw;
	}
}

pair<int, int> get_mx(int l, int r){
	if(r < l) return {-2e9, 0};
	int k = lw[r - l + 1];
	return max(mx[k][r], mx[k][l + (1 << k) - 1]);
}

pair<int, int> get_mn(int l, int r){
	if(r < l) return {2e9, 0};
	int k = lw[r - l + 1];
	return min(mn[k][r], mn[k][l + (1 << k) - 1]);
}

int get_first(int L, vector<int>& pre){
	int lo = L;
	int hi = N - 1;
	int bst = -1;
	int beat = 0;
	if(L > 0) beat = pre[L-1];
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(pre[mid] > beat){
			bst = mid;
			hi = mid - 1;
		}else lo = mid + 1;
	}
	assert(bst != -1);
	return bst;
}

int get_last(int R, vector<int>& pre){
	int lo = 0;
	int hi = R;
	int bst = -1;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(pre[mid] <= pre[R] - 1){
			bst = mid;
			lo = mid + 1;
		}else hi = mid - 1;
	}
	return bst + 1;
}

void init(int n, vector<int> H1) {
	N = n;
	H = H1;
	first = 1;
	precalcmx();
	precalcmn();
	precalclw();
}

int dnc(int L, int R, int D) {
	if(L == R) {
		return H[L];
	}else if(L > R){
		return 2e9;
	}
	pair<int, int> pr = get_mx(L, R);
	int mx = pr.first;
	int ind = pr.second;
	int mn1 = dnc(ind + 1, R, D);
	int mn2 = dnc(L, ind - 1, D);
	candidates.push_back({min(mx - mn1, mx - mn2), ind});
	return min(mn1, mn2);
}

int max_towers(int L, int R, int D) {
	if(first == 1){
		dnc(0, N-1, D);
		sort(candidates.begin(), candidates.end());
		reverse(candidates.begin(), candidates.end());
		vector<int> good(N, 0);
		for(int l = 0; l < (int)candidates.size(); l += B){
			for(int i = l; i < min(l + B, (int)candidates.size()); i++){
				good[candidates[i].second] = 1;
			}
			vector<int> pre(N);
			for(int i = 0; i < N; i++){
				if(i == 0) pre[i] = good[i];
				else pre[i] = pre[i-1] + good[i];
			}
			prefix.push_back(pre);
		}
		first = 0;
	}
	for(int l = 0; l < (int)candidates.size(); l += B){
		int indmx = l + B - 1;
		if(indmx >= (int)candidates.size()) indmx = (int)candidates.size() - 1;
		if(candidates[indmx].first >= D && l < (int)candidates.size() - 1) continue;
		int total = 0;
		int ind1 = N;
		int ind2 = -1;
		if(l != 0){
			int i = l / B - 1;
			total = prefix[i][R];
			if(L > 0) total -= prefix[i][L-1];
			if(total > 0){
				ind1 = get_first(L, prefix[i]);
				ind2 = get_last(R, prefix[i]);
			}
		}
		for(int i = l; candidates[i].first >= D; i++){
			int ind = candidates[i].second;
			if(ind >= L && ind <= R){
				total++;
				ind1 = min(ind1, ind);
				ind2 = max(ind2, ind);
			}
		}
		if(total == 0) return 1;
		else if(total == 1){
			int ind = ind1;
			int mn1 = get_mn(L, ind - 1).first;
			int mn2 = get_mn(ind + 1, R).first;
			if(mn1 <= H[ind] - D && mn2 <= H[ind] - D) return 2;
			else return 1;
		}else{
			int ans = total + 1;
			int ind = ind1;
			int mn = get_mn(L, ind - 1).first;
			if(mn > H[ind]  - D) ans--;
			ind = ind2;
			mn = get_mn(ind + 1, R).first;
			if(mn > H[ind] - D) ans--;
			return ans;	
		}
	}
}

// int main() {
//   int N, Q;
//   assert(2 == scanf("%d %d", &N, &Q));
//   std::vector<int> H(N);
//   for (int i = 0; i < N; ++i) {
//     assert(1 == scanf("%d", &H[i]));
//   }
//   init(N, H);
//   for (int i = 0; i < Q; ++i) {
//     int L, R, D;
//     assert(3 == scanf("%d %d %d", &L, &R, &D));
//     printf("%d\n", max_towers(L, R, D));
//   }
//   return 0;
// }

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:184:1: warning: control reaches end of non-void function [-Wreturn-type]
  184 | }
      | ^

• 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