Submission #827252

#	Time	Username	Problem	Language	Result	Execution time	Memory
827252		esomer	Radio Towers (IOI22_towers)	C++17	18 / 100	864 ms	42804 KiB

towers

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

using namespace std;

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

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){
	int lo = L;
	int hi = N - 1;
	int bst;
	int beat = 0;
	if(L > 0) beat = prefix[L-1];
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(prefix[mid] > beat){
			bst = mid;
			hi = mid - 1;
		}else lo = mid + 1;
	}
	return bst;
}

int get_last(int R){
	int lo = 0;
	int hi = R;
	int bst = -1;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(prefix[mid] <= prefix[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;
	good.assign(N, 0);
	spec = 0;
	first = 1;
	bool asc = 1;
	for(int i = 1; i < N; i++){
		if(spec == -1) break;
		if(H[i] > H[i-1]){
			if(asc) spec = i;
			else spec = -1;
		}else{
			asc = 0;
		}
	}
	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);
	if(mn1 <= mx - D && mn2 <= mx - D) good[ind] = 1;
	candidates.push_back({min(mx - mn1, mx - mn2), ind});
	return min(mn1, mn2);
}

int max_towers(int L, int R, int D) {
	if(spec == -1){
		if(first == 1){
			dnc(0, N-1, D);
			sort(candidates.begin(), candidates.end());
			prefix.resize(N);
			for(int i = 0; i < N; i++){
				if(i == 0) prefix[i] = good[i];
				else prefix[i] = prefix[i-1] + good[i];
			}
			first = 0;
		}
		if(L == 0 && R == N - 1){
			int lo = 0;
			int hi = (int)candidates.size() - 1;
			int bst = N;
			while(lo <= hi){
				int mid = (lo + hi) / 2;
				if(candidates[mid].first >= D){
					bst = mid;
					hi = mid - 1;
				}else lo = mid + 1;
			}
			return (int)candidates.size() - bst + 1;
		}else{
			int total = prefix[R];
			if(L > 0) total -= prefix[L - 1];
			if(total == 0) return 1;
			else if(total == 1){
				int ind = get_first(L);
				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 = get_first(L);
				int mn = get_mn(L, ind - 1).first;
				if(mn > H[ind]  - D) ans--;
				ind = get_last(R);
				mn = get_mn(ind + 1, R).first;
				if(mn > H[ind] - D) ans--;
				return ans;	
			}
		}
	}else{
		int ans = 1;
		if(L < spec && R > spec && H[L] <= H[spec] - D && H[R] <= H[spec] - 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 get_first(int)':
towers.cpp:78:9: warning: 'bst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |  return bst;
      |         ^~~

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