제출 #1056726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1056726		AmirAli_H1	송신탑 (IOI22_towers)	C++17	23 / 100	4073 ms	5076 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 ll oo = 1e9 + 7;

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

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];
}

bool check(int i, int j, int D) {
	if (j - i + 1 <= 2) return 0;
	int mx = *max_element(A + i + 1, A + 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;
	
	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