55772023-08-01 15:26:50111Mágikus intervallumcpp14Wrong answer 25/10089ms32792 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;
}























SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Accepted71ms9332 KiB
subtask20/5
3Accepted3ms3540 KiB
4Accepted3ms3776 KiB
5Accepted3ms3972 KiB
6Accepted3ms4180 KiB
7Wrong answer3ms4300 KiB
8Accepted3ms4272 KiB
subtask30/10
9Accepted3ms4548 KiB
10Wrong answer3ms4656 KiB
11Accepted3ms4768 KiB
12Wrong answer3ms4872 KiB
13Accepted3ms5160 KiB
14Accepted3ms5240 KiB
subtask410/10
15Accepted3ms5256 KiB
16Accepted3ms5352 KiB
17Accepted3ms5596 KiB
18Accepted8ms6540 KiB
19Accepted74ms14184 KiB
20Accepted43ms14788 KiB
21Accepted43ms15548 KiB
subtask515/15
22Accepted2ms8532 KiB
23Accepted43ms15624 KiB
24Accepted59ms18620 KiB
subtask60/60
25Accepted71ms17644 KiB
26Accepted81ms19820 KiB
27Wrong answer81ms21268 KiB
28Wrong answer76ms21708 KiB
29Wrong answer81ms23040 KiB
30Wrong answer78ms24372 KiB
31Wrong answer87ms26864 KiB
32Wrong answer89ms28412 KiB
33Accepted50ms28908 KiB
34Accepted50ms29840 KiB
35Wrong answer50ms30508 KiB
36Accepted75ms31912 KiB
37Accepted37ms32176 KiB
38Accepted43ms32792 KiB
39Accepted3ms25812 KiB