Submission #1056733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056733		AmirAli_H1	Radio Towers (IOI22_towers)	C++17	23 / 100	4065 ms	12912 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 = 1e5 + 7;
const int maxlg = 20;
const ll oo = 1e9 + 7;

int n;
ll Ax[maxn], A[maxn]; set<int> st;
int arr[maxn], rmq[maxn][maxlg];

bool cmp(int i, int j) {
	return (A[i] < A[j]);
}

void init(int N, vector<int> H) {
	n = N;
	for (int i = 0; i < n; i++) Ax[i] = H[i];
}

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

bool check(int i, int j, int D) {
	if (j - i + 1 <= 2) return 0;
	int mx = get_max(i + 1, j);
	return (mx >= max(A[i], A[j]) + D);
}

bool ok(int i, int D) {
	auto it = st.lower_bound(i);
	if (it != st.end()) {
		if (!check(i, *it, D)) return 0;
	}
	if (it != st.begin()) {
		it--;
		if (!check(*it, i, D)) return 0;
	}
	return 1;
}

int max_towers(int L, int R, int D) {
	for (int j = L; j <= R; j++) A[j - L] = Ax[j];
	n = R - L + 1;
	
	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]);
		}
	}
	
	st.clear();
	iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
	for (int j = 0; j < n; j++) {
		int i = arr[j];
		if (ok(i, D)) st.insert(i);
	}
	
	return len(st);
}

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