55802023-08-01 16:57:45111Mágikus intervallumcpp14Wrong answer 30/100159ms103344 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);
	// sparse table for min index query for ps and ss
	int M = N + 1;
	vector<vector<int>> pst(__lg(M) + 1, vector<int>(M));
	vector<vector<int>> sst(__lg(M) + 1, vector<int>(M));
	iota(pst[0].begin(), pst[0].end(), 0);
	iota(sst[0].begin(), sst[0].end(), 0);
	for (int i = 1; (1 << i) <= M; i++) {
		for (int j = 0; j + (1 << i) <= M; j++) {
			pst[i][j] = ps[pst[i - 1][j]] < ps[pst[i - 1][j + (1 << i - 1)]] ? pst[i - 1][j] : pst[i - 1][j + (1 << i - 1)];
			sst[i][j] = ss[sst[i - 1][j]] < ss[sst[i - 1][j + (1 << i - 1)]] ? sst[i - 1][j] : sst[i - 1][j + (1 << i - 1)];
		}
	}
	// [l, r)
	function<int(int, int)> ps_min = [&](int l, int r) {
		if (l == r) {
			return r;
		}
		int i = __lg(r - l);
		return ps[pst[i][l]] < ps[pst[i][r - (1 << i)]] ? pst[i][l] : pst[i][r - (1 << i)];
	};
	function<int(int, int)> ss_min = [&](int l, int r) {
		if (l == r) {
			return r;
		}
		int i = __lg(r - l);
		return ss[sst[i][l]] < ss[sst[i][r - (1 << i)]] ? sst[i][l] : sst[i][r - (1 << i)];
	};
	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 = ss_min(p[i] + 1, s0);
			int e1 = ps_min(e0 + 1, n[i]);
			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 = ss_min(p[i] + 1, s1);
			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 = ps_min(e1 + 1, n[i]);
			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
1Accepted3ms2088 KiB
2Accepted116ms83940 KiB
subtask25/5
3Accepted3ms2240 KiB
4Accepted3ms2484 KiB
5Accepted3ms2664 KiB
6Accepted3ms2764 KiB
7Accepted3ms3240 KiB
8Accepted3ms3276 KiB
subtask30/10
9Accepted3ms3440 KiB
10Wrong answer3ms3840 KiB
11Accepted3ms3652 KiB
12Accepted3ms3656 KiB
13Accepted3ms4012 KiB
14Accepted3ms4060 KiB
subtask410/10
15Accepted3ms3828 KiB
16Accepted2ms3864 KiB
17Accepted3ms4176 KiB
18Accepted9ms8832 KiB
19Accepted130ms102200 KiB
20Accepted103ms102452 KiB
21Accepted103ms102756 KiB
subtask515/15
22Accepted2ms4260 KiB
23Accepted93ms90352 KiB
24Accepted109ms102784 KiB
subtask60/60
25Accepted118ms90480 KiB
26Accepted151ms102824 KiB
27Accepted150ms102864 KiB
28Accepted140ms90576 KiB
29Wrong answer153ms90828 KiB
30Wrong answer136ms90796 KiB
31Accepted159ms103036 KiB
32Accepted158ms103080 KiB
33Accepted115ms103032 KiB
34Accepted114ms103088 KiB
35Accepted115ms103032 KiB
36Accepted149ms103344 KiB
37Accepted115ms103300 KiB
38Accepted119ms103300 KiB
39Accepted3ms5040 KiB