제출 #1056515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1056515		AmirAli_H1	Radio Towers (IOI22_towers)	C++17	0 / 100	4097 ms	4560 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 ll oo = 1e9 + 7;
const int maxn = 1e5 + 7;

int n;
ll A[maxn]; int M[maxn], Mx[maxn];
vector<int> ls, lsx; ll val[maxn];

void init(int N, vector<int> H) {
	n = N;
	for (int i = 0; i < n; i++) A[i] = H[i];
	
	for (int i = 0; i < n; i++) {
		val[i] = 0;
		if ((i - 1 >= 0 && A[i] > A[i - 1]) && (i + 1 < n && A[i] > A[i + 1])) {
			M[i] = 1; Mx[i] = 1;
		}
		else if ((i - 1 >= 0 && A[i] < A[i - 1]) && (i + 1 < n && A[i] < A[i + 1])) {
			M[i] = 1; Mx[i] = -1;
		}
		if (M[i]) ls.pb(i);
	}
	
	while (len(ls) > 1) {
		ll mn = oo;
		for (int j = 1; j < len(ls); j++) {
			int j1 = ls[j - 1], j2 = ls[j];
			mn = min(mn, abs(A[j1] - A[j2]));
		}
		for (int j = 1; j < len(ls); j++) {
			int j1 = ls[j - 1], j2 = ls[j];
			if (abs(A[j1] - A[j2]) == mn) {
				M[j1] = 0; M[j2] = 0;
				val[j1] = mn; val[j2] = mn;
			}
		}
		lsx.clear();
		for (int j : ls) {
			if (M[j]) lsx.pb(j);
		}
		ls = lsx;
	}
	if (len(ls) >= 1) val[ls[0]] = oo;
}

int get_min(int L, int R) {
	ll mn = oo;
	for (int j = L; j <= R; j++) mn = min(mn, A[j]);
	return mn;
}

int max_towers(int L, int R, int D) {
	int lx = R + 1, rx = L - 1;
	
	lsx.clear();
	for (int j = L; j <= R; j++) {
		if (val[j] >= D) {
			lx = min(lx, j); rx = max(rx, j);
			lsx.pb(j);
		}
	}
	if (len(lsx) <= 1) return 1;
	
	int t = len(lsx) / 2;
	if (Mx[lsx[0]] == -1 && Mx[lsx.back()] == -1) t++;
	
	if (Mx[lsx[0]] == 1 && get_min(L, lx - 1) <= A[lsx[0]] - D) t++;
	if (Mx[lsx.back()] == 1 && get_min(rx + 1, R) <= A[lsx.back()] - D) t++;
	return t;
}

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