5577 2023. 08. 01 15:26:50 111 Mágikus intervallum cpp14 Hibás válasz 25/100 89ms 32792 KiB
#include <bits/extc++.h>
using namespace std;

#define int long long

#define pii pair<int, int>

void prev_greater(vector<int>& r, const vector<int>& a) {
	stack<int> s;
	for (int i = 0; i < a.size(); i++) {
		while (!s.empty() && a[s.top()] <= a[i]) {
			s.pop();
		}
		r[i] = s.empty() ? -1 : s.top();
		s.push(i);
	}
}

void next_greater(vector<int>& r, const vector<int>& a) {
	stack<int> s;
	for (int i = a.size() - 1; i >= 0; i--) {
		while (!s.empty() && a[s.top()] <= a[i]) {
			s.pop();
		}
		r[i] = s.empty() ? a.size() : s.top();
		s.push(i);
	}
}

signed main() {
#ifdef CB
	ifstream fin("be2.txt");
	cin.rdbuf(fin.rdbuf());
	ofstream fout("ki.txt");
#endif
	int N;
	cin >> N;
	vector<int> v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	vector<int> p(N), n(N);
	prev_greater(p, v);
	next_greater(n, v);
	int ans = 0;
	int ms, me;
	for (int i = 0; i < N; i++) {
		int s = i, e = i;
		int m = v[i];
		while (true) {
			bool bs = s - 1 > p[i] && m + v[s - 1] <= v[i] * 2;
			bool be = e + 1 < n[i] && m + v[e + 1] <= v[i] * 2;
			if (bs && be) {
				if (v[s - 1] <= v[e + 1]) {
					s--;
					m += v[s];
				}
				else {
					e++;
					m += v[e];
				}
			}
			else if (bs) {
				s--;
				m += v[s];
			}
			else if (be) {
				e++;
				m += v[e];
			}
			else {
				break;
			}
		}
		if (ans < e - s + 1) {
			ans = e - s + 1;
			ms = s;
			me = e;
		}
	}
	cout << ms + 1 << " " << me + 1 << endl;
	return 0;
}























Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1812 KiB
2 Elfogadva 71ms 9332 KiB
subtask2 0/5
3 Elfogadva 3ms 3540 KiB
4 Elfogadva 3ms 3776 KiB
5 Elfogadva 3ms 3972 KiB
6 Elfogadva 3ms 4180 KiB
7 Hibás válasz 3ms 4300 KiB
8 Elfogadva 3ms 4272 KiB
subtask3 0/10
9 Elfogadva 3ms 4548 KiB
10 Hibás válasz 3ms 4656 KiB
11 Elfogadva 3ms 4768 KiB
12 Hibás válasz 3ms 4872 KiB
13 Elfogadva 3ms 5160 KiB
14 Elfogadva 3ms 5240 KiB
subtask4 10/10
15 Elfogadva 3ms 5256 KiB
16 Elfogadva 3ms 5352 KiB
17 Elfogadva 3ms 5596 KiB
18 Elfogadva 8ms 6540 KiB
19 Elfogadva 74ms 14184 KiB
20 Elfogadva 43ms 14788 KiB
21 Elfogadva 43ms 15548 KiB
subtask5 15/15
22 Elfogadva 2ms 8532 KiB
23 Elfogadva 43ms 15624 KiB
24 Elfogadva 59ms 18620 KiB
subtask6 0/60
25 Elfogadva 71ms 17644 KiB
26 Elfogadva 81ms 19820 KiB
27 Hibás válasz 81ms 21268 KiB
28 Hibás válasz 76ms 21708 KiB
29 Hibás válasz 81ms 23040 KiB
30 Hibás válasz 78ms 24372 KiB
31 Hibás válasz 87ms 26864 KiB
32 Hibás válasz 89ms 28412 KiB
33 Elfogadva 50ms 28908 KiB
34 Elfogadva 50ms 29840 KiB
35 Hibás válasz 50ms 30508 KiB
36 Elfogadva 75ms 31912 KiB
37 Elfogadva 37ms 32176 KiB
38 Elfogadva 43ms 32792 KiB
39 Elfogadva 3ms 25812 KiB