55802023-08-01 16:57:45111Mágikus intervallumcpp14Hibás válasz 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;
}























RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms2088 KiB
2Elfogadva116ms83940 KiB
subtask25/5
3Elfogadva3ms2240 KiB
4Elfogadva3ms2484 KiB
5Elfogadva3ms2664 KiB
6Elfogadva3ms2764 KiB
7Elfogadva3ms3240 KiB
8Elfogadva3ms3276 KiB
subtask30/10
9Elfogadva3ms3440 KiB
10Hibás válasz3ms3840 KiB
11Elfogadva3ms3652 KiB
12Elfogadva3ms3656 KiB
13Elfogadva3ms4012 KiB
14Elfogadva3ms4060 KiB
subtask410/10
15Elfogadva3ms3828 KiB
16Elfogadva2ms3864 KiB
17Elfogadva3ms4176 KiB
18Elfogadva9ms8832 KiB
19Elfogadva130ms102200 KiB
20Elfogadva103ms102452 KiB
21Elfogadva103ms102756 KiB
subtask515/15
22Elfogadva2ms4260 KiB
23Elfogadva93ms90352 KiB
24Elfogadva109ms102784 KiB
subtask60/60
25Elfogadva118ms90480 KiB
26Elfogadva151ms102824 KiB
27Elfogadva150ms102864 KiB
28Elfogadva140ms90576 KiB
29Hibás válasz153ms90828 KiB
30Hibás válasz136ms90796 KiB
31Elfogadva159ms103036 KiB
32Elfogadva158ms103080 KiB
33Elfogadva115ms103032 KiB
34Elfogadva114ms103088 KiB
35Elfogadva115ms103032 KiB
36Elfogadva149ms103344 KiB
37Elfogadva115ms103300 KiB
38Elfogadva119ms103300 KiB
39Elfogadva3ms5040 KiB