55782023-08-01 16:25:19111Mágikus intervallumcpp14Wrong answer 5/100944ms16116 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;
}























SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1684 KiB
2Accepted104ms12120 KiB
subtask25/5
3Accepted3ms2144 KiB
4Accepted2ms2184 KiB
5Accepted3ms2280 KiB
6Accepted3ms2364 KiB
7Accepted3ms2512 KiB
8Accepted3ms2604 KiB
subtask30/10
9Accepted3ms2728 KiB
10Wrong answer3ms2940 KiB
11Accepted3ms3020 KiB
12Accepted3ms3020 KiB
13Accepted4ms3300 KiB
14Accepted3ms3504 KiB
subtask40/10
15Accepted3ms3680 KiB
16Accepted3ms3792 KiB
17Accepted7ms3824 KiB
18Accepted527ms4564 KiB
19Time limit exceeded879ms9052 KiB
20Time limit exceeded865ms8988 KiB
21Time limit exceeded857ms9116 KiB
subtask50/15
22Accepted3ms3984 KiB
23Time limit exceeded899ms8488 KiB
24Time limit exceeded899ms10092 KiB
subtask60/60
25Accepted107ms14664 KiB
26Accepted119ms15916 KiB
27Accepted118ms16116 KiB
28Time limit exceeded861ms8976 KiB
29Time limit exceeded852ms8980 KiB
30Time limit exceeded865ms8820 KiB
31Time limit exceeded870ms9696 KiB
32Time limit exceeded874ms9512 KiB
33Time limit exceeded865ms9448 KiB
34Time limit exceeded857ms9452 KiB
35Time limit exceeded865ms9448 KiB
36Time limit exceeded925ms9392 KiB
37Time limit exceeded944ms9504 KiB
38Time limit exceeded857ms9456 KiB
39Accepted3ms4436 KiB