Submission #631054

#	Time	Username	Problem	Language	Result	Execution time	Memory
631054		rainboy	Radio Towers (IOI22_towers)	C++17	60 / 100	1000 ms	1888 KiB

towers

#include "towers.h"
#include <vector>

using namespace std;

const int N = 100000;

int max(int a, int b) { return a > b ? a : b; }

typedef vector<int> vi;

int aa[N], ii[N], ll[N], rr[N], n, p, cnt;
int first;

void init(int n_, vi aa_) {
	n = n_;
	for (int i = 0; i < n; i++)
		aa[i] = aa_[i];
	p = 0;
	while (p < n - 1 && aa[p] < aa[p + 1])
		p++;
	for (int i = p + 1; i < n; i++)
		if (aa[i - 1] < aa[i]) {
			p = -1;
			break;
		}
	first = 1;
}

int max_towers(int l, int r, int d) {
	if (p != -1)
		return l < p && p < r && aa[p] - aa[l] >= d && aa[p] - aa[r] >= d ? 2 : 1;
	else {
		if (first) {
			cnt = 0;
			ii[cnt++] = 0;
			for (int i = 1; i < n; i++)
				if (cnt % 2 != 0) {
					if (aa[ii[cnt - 1]] > aa[i])
						ii[cnt - 1] = i;
					else if (aa[i] - aa[ii[cnt - 1]] >= d)
						ii[cnt++] = i;
				} else {
					if (aa[ii[cnt - 1]] < aa[i])
						ii[cnt - 1] = i;
					else if (aa[ii[cnt - 1]] - aa[i] >= d)
						ii[cnt++] = i;
				}
			for (int h = 1; h < cnt - 1; h += 2) {
				for (int i = ii[h] - 1; i >= 0; i--)
					if (aa[ii[h]] - aa[i] >= d) {
						ll[h / 2] = i;
						break;
					}
				for (int i = ii[h] + 1; i < n; i++)
					if (aa[ii[h]] - aa[i] >= d) {
						rr[h / 2] = i;
						break;
					}
			}
			cnt = (cnt - 1) / 2;
			first = 0;
		}
		int lower, upper;
		lower = -1, upper = cnt;
		while (upper - lower > 1) {
			int h = (lower + upper) / 2;
			if (l <= ll[h])
				upper = h;
			else
				lower = h;
		}
		l = upper;
		lower = -1, upper = cnt;
		while (upper - lower > 1) {
			int h = (lower + upper) / 2;
			if (rr[h] <= r)
				lower = h;
			else
				upper = h;
		}
		r = lower;
		return max(r - l + 1, 0) + 1;
	}
}

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