Submission #1059164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059164		AmirAli_H1	Radio Towers (IOI22_towers)	C++17	17 / 100	572 ms	13104 KiB

towers

// In the name of Allah

#include <bits/stdc++.h>
#include "towers.h"
using namespace std;

typedef			long long				ll;
typedef			pair<int, int>			pii;
typedef			pair<ll, ll>			pll;

#define			F						first
#define			S						second
#define			all(x)					(x).begin(),(x).end()
#define			len(x)					((ll) (x).size())
#define			Mp						make_pair
#define			pb						push_back
#define			endl					'\n'
#define			sep						' '

const int maxn = 2e5 + 7;
const int maxlg = 20;
const ll oo = 1e9 + 7;

int n;
ll A[maxn]; int L[maxn], R[maxn];
int rmq[maxn][maxlg];
vector<ll> arr; ll sm[maxn];

int GI(ll x) {
	return lower_bound(all(arr), x) - arr.begin();
}

ll get_max(int l, int r) {
	if (l >= r) return -oo;
	int j = __lg(r - l);
	return max(rmq[l][j], rmq[r - (1 << j)][j]);
}

void init(int N, vector<int> H) {
	n = N;
	for (int i = 0; i < n; i++) A[i] = H[i];
	for (int i = n - 1; i >= 0; i--) {
		rmq[i][0] = A[i];
		for (int j = 1; j < maxlg; j++) {
			if (i + (1 << j) - 1 >= n) break;
			rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (L[i] = i - 1; L[i] != -1 && A[i] <= A[L[i]]; L[i] = L[L[i]]);
	}
	for (int i = n - 1; i >= 0; i--) {
		for (R[i] = i + 1; R[i] != n && A[i] <= A[R[i]]; R[i] = R[R[i]]);
	}
	
	arr.pb(oo);
	for (int i = 0; i < n; i++) {
		if (L[i] != -1) {
			ll valx = get_max(L[i] + 1, i + 1) - A[i];
			if (valx >= 1) arr.pb(valx);
		}
		if (R[i] != n) {
			ll valx = get_max(i, R[i]) - A[i];
			if (valx >= 1) arr.pb(valx);
		}
	}
	sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());
	
	for (int i = 0; i < n; i++) {
		ll x = oo;
		if (L[i] != -1) x = min(x, get_max(L[i] + 1, i + 1) - A[i]);
		if (R[i] != n) x = min(x, get_max(i, R[i]) - A[i]);
		if (x == 0) continue;
		int j = GI(x); sm[j]++;
	}
	
	for (int j = len(arr) - 2; j >= 0; j--) sm[j] += sm[j + 1];
}

int max_towers(int L, int R, int D) {
	int j = lower_bound(all(arr), D) - arr.begin();
	return sm[j];
}

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