91382024-02-15 19:03:50111A Barbárcpp17Wrong answer 47/1001.077s379868 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef CB
	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	int N;
	cin >> N;
	vector<int> v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	vector<int> a(N);
	vector<int> b(N);
	for (int i = 1; i <= N - 2; i++) {
		a[i] = lower_bound(v.begin(), v.end(), v[i] * 2 - v[i - 1]) - v.begin() - 1;
		b[i] = lower_bound(v.begin(), v.end(), v[i] * 2 - v[i + 1]) - v.begin();
	}
	vector<array<int, 20>> spt(N);
	for (int i = 0; i < N; i++) {
		spt[i][0] = a[i];
	}
	for (int j = 1; j < 20; j++) {
		for (int l = 0, r = 1 << j - 1; r < N; l++, r++) {
			spt[l][j] = max(spt[l][j - 1], spt[r][j - 1]);
		}
	}
	auto query = [&](int l, int r) -> int {
		if (l == r) {
			return -1;
		}
		int i = __lg(r - l);
		return max(spt[l][i], spt[r - (1 << i)][i]);
	};
	vector<int> ans(N);
	ans[0] = N - 1;
	ans[N - 1] = 0;
	vector<int> s;
	for (int i = N - 2; i >= 1; i--) {
		while (!s.empty() && b[s.back()] >= b[i]) {
			s.pop_back();
		}
		s.push_back(i);
		ans[i] = N - 1;
		int x = query(0, b[s.front()] + 1);
		if (x > s.front()) {
			ans[i] = 0;
			continue;
		}
		if (b[s.front()] == i) {
			ans[i] = 0;
			continue;
		}
		for (int j = 1; j < s.size(); j++) {
			int y = query(b[s.front()] + 1, b[s[j]] + 1);
			if (j + 1 < s.size() && query(b[s[j]] + 1, b[s[j + 1]] + 1) <= s[j + 1]) {
				continue;
			}
			if (y <= s[j] && x > s[j]) {
				ans[i] = 0;
				break;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		cout << ans[i] << ' ';
	}
	cout << '\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Accepted3ms2024 KiB
subtask212/12
3Accepted2ms2100 KiB
4Accepted3ms2240 KiB
5Accepted3ms2448 KiB
6Accepted3ms2676 KiB
7Accepted3ms2876 KiB
8Accepted3ms3108 KiB
9Accepted3ms3032 KiB
10Accepted2ms3116 KiB
11Accepted3ms3216 KiB
12Accepted3ms3092 KiB
subtask30/28
13Accepted3ms3360 KiB
14Accepted3ms3392 KiB
15Accepted3ms3192 KiB
16Accepted3ms3196 KiB
17Accepted3ms3200 KiB
18Accepted3ms3200 KiB
19Accepted3ms3600 KiB
20Wrong answer3ms3488 KiB
21Accepted3ms3488 KiB
subtask435/35
22Accepted74ms40648 KiB
23Accepted82ms40836 KiB
24Accepted74ms41096 KiB
25Accepted72ms40864 KiB
26Accepted41ms25016 KiB
27Accepted65ms40896 KiB
28Accepted65ms40832 KiB
29Accepted65ms40856 KiB
30Accepted67ms40856 KiB
31Accepted74ms40836 KiB
subtask50/25
32Time limit exceeded1.024s378884 KiB
33Accepted776ms341392 KiB
34Time limit exceeded1.031s379152 KiB
35Wrong answer768ms341528 KiB
36Wrong answer981ms363744 KiB
37Accepted801ms379868 KiB
38Accepted934ms372252 KiB
39Accepted802ms379816 KiB
40Accepted957ms379624 KiB
41Time limit exceeded1.034s378608 KiB
42Accepted795ms365448 KiB
43Accepted977ms374196 KiB
44Time limit exceeded1.021s378660 KiB
45Accepted842ms377124 KiB
46Accepted829ms377116 KiB
47Time limit exceeded1.072s191604 KiB
48Time limit exceeded1.077s191596 KiB
49Time limit exceeded1.072s191372 KiB
50Time limit exceeded1.075s191460 KiB