5578 2023. 08. 01 16:25:19 111 Mágikus intervallum cpp14 Hibás válasz 5/100 944ms 16116 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);
	}
}

void pref_sum(vector<int>& r, const vector<int>& a) {
	for (int i = 0; i < a.size(); i++) {
		r[i + 1] = r[i] + a[i];
	}
}

void suff_sum(vector<int>& r, const vector<int>& a) {
	for (int i = a.size() - 1; i >= 0; i--) {
		r[i] = r[i + 1] + a[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);
	vector<int> ps(N + 1), ss(N + 1);
	prev_greater(p, v);
	next_greater(n, v);
	pref_sum(ps, v);
	suff_sum(ss, v);
	int ans = 0;
	int ms, me;
	for (int i = 0; i < N; i++) {
		int s0 = i, e0 = i;
		int m0 = v[i];
		while (true) {
			int s1 = min_element(ss.begin() + p[i] + 1, ss.begin() + s0) - ss.begin();
			int e1 = min_element(ps.begin() + e0 + 1, ps.begin() + n[i]) - ps.begin();
			int sd = ss[s1] - ss[s0];
			int ed = ps[e1 + 1] - ps[e0 + 1];
			bool bs = s0 > s1 && s1 > p[i] && m0 + sd <= v[i] * 2;
			bool be = e0 < e1 && e1 < n[i] && m0 + ed <= v[i] * 2;
			if (bs && be) {
				if (sd <= ed) {
					s0 = s1;
					m0 += sd;
				}
				else {
					e0 = e1;
					m0 += ed;
				}
			}
			else if (bs) {
				s0 = s1;
				m0 += sd;
			}
			else if (be) {
				e0 = e1;
				m0 += ed;
			}
			else {
				break;
			}
		}
		if (ans < e0 - s0 + 1) {
			ans = e0 - s0 + 1;
			ms = s0;
			me = e0;
		}
		int s1 = s0, e1 = e0, m1 = m0;
		while (e1 > i) {
			m1 -= v[e1];
			e1--;
		nxt:
			int s2 = min_element(ss.begin() + p[i] + 1, ss.begin() + s1) - ss.begin();
			int sd = ss[s2] - ss[s1];
			bool bs = s1 > s2 && s2 > p[i] && m1 + sd <= v[i] * 2;
			if (bs) {
				s1 = s2;
				m1 += sd;
				goto nxt;
			}
			if (ans < e1 - s1 + 1) {
				ans = e1 - s1 + 1;
				ms = s1;
				me = e1;
			}
		}
		s1 = s0, e1 = e0, m1 = m0;
		while (s1 < i) {
			m1 -= v[s1];
			s1++;
		nxt2:
			int e2 = min_element(ps.begin() + e1 + 1, ps.begin() + n[i]) - ps.begin();
			int ed = ps[e2 + 1] - ps[e1 + 1];
			bool be = e1 < e2 && e2 < n[i] && m1 + ed <= v[i] * 2;
			if (be) {
				e1 = e2;
				m1 += ed;
				goto nxt2;
			}
			if (ans < e1 - s1 + 1) {
				ans = e1 - s1 + 1;
				ms = s1;
				me = e1;
			}
		}
	}
	cout << ms + 1 << " " << me + 1 << endl;
	return 0;
}























Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1684 KiB
2 Elfogadva 104ms 12120 KiB
subtask2 5/5
3 Elfogadva 3ms 2144 KiB
4 Elfogadva 2ms 2184 KiB
5 Elfogadva 3ms 2280 KiB
6 Elfogadva 3ms 2364 KiB
7 Elfogadva 3ms 2512 KiB
8 Elfogadva 3ms 2604 KiB
subtask3 0/10
9 Elfogadva 3ms 2728 KiB
10 Hibás válasz 3ms 2940 KiB
11 Elfogadva 3ms 3020 KiB
12 Elfogadva 3ms 3020 KiB
13 Elfogadva 4ms 3300 KiB
14 Elfogadva 3ms 3504 KiB
subtask4 0/10
15 Elfogadva 3ms 3680 KiB
16 Elfogadva 3ms 3792 KiB
17 Elfogadva 7ms 3824 KiB
18 Elfogadva 527ms 4564 KiB
19 Időlimit túllépés 879ms 9052 KiB
20 Időlimit túllépés 865ms 8988 KiB
21 Időlimit túllépés 857ms 9116 KiB
subtask5 0/15
22 Elfogadva 3ms 3984 KiB
23 Időlimit túllépés 899ms 8488 KiB
24 Időlimit túllépés 899ms 10092 KiB
subtask6 0/60
25 Elfogadva 107ms 14664 KiB
26 Elfogadva 119ms 15916 KiB
27 Elfogadva 118ms 16116 KiB
28 Időlimit túllépés 861ms 8976 KiB
29 Időlimit túllépés 852ms 8980 KiB
30 Időlimit túllépés 865ms 8820 KiB
31 Időlimit túllépés 870ms 9696 KiB
32 Időlimit túllépés 874ms 9512 KiB
33 Időlimit túllépés 865ms 9448 KiB
34 Időlimit túllépés 857ms 9452 KiB
35 Időlimit túllépés 865ms 9448 KiB
36 Időlimit túllépés 925ms 9392 KiB
37 Időlimit túllépés 944ms 9504 KiB
38 Időlimit túllépés 857ms 9456 KiB
39 Elfogadva 3ms 4436 KiB