55772023-08-01 15:26:50111Mágikus intervallumcpp14Hibás válasz 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;
}























RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Elfogadva71ms9332 KiB
subtask20/5
3Elfogadva3ms3540 KiB
4Elfogadva3ms3776 KiB
5Elfogadva3ms3972 KiB
6Elfogadva3ms4180 KiB
7Hibás válasz3ms4300 KiB
8Elfogadva3ms4272 KiB
subtask30/10
9Elfogadva3ms4548 KiB
10Hibás válasz3ms4656 KiB
11Elfogadva3ms4768 KiB
12Hibás válasz3ms4872 KiB
13Elfogadva3ms5160 KiB
14Elfogadva3ms5240 KiB
subtask410/10
15Elfogadva3ms5256 KiB
16Elfogadva3ms5352 KiB
17Elfogadva3ms5596 KiB
18Elfogadva8ms6540 KiB
19Elfogadva74ms14184 KiB
20Elfogadva43ms14788 KiB
21Elfogadva43ms15548 KiB
subtask515/15
22Elfogadva2ms8532 KiB
23Elfogadva43ms15624 KiB
24Elfogadva59ms18620 KiB
subtask60/60
25Elfogadva71ms17644 KiB
26Elfogadva81ms19820 KiB
27Hibás válasz81ms21268 KiB
28Hibás válasz76ms21708 KiB
29Hibás válasz81ms23040 KiB
30Hibás válasz78ms24372 KiB
31Hibás válasz87ms26864 KiB
32Hibás válasz89ms28412 KiB
33Elfogadva50ms28908 KiB
34Elfogadva50ms29840 KiB
35Hibás válasz50ms30508 KiB
36Elfogadva75ms31912 KiB
37Elfogadva37ms32176 KiB
38Elfogadva43ms32792 KiB
39Elfogadva3ms25812 KiB