5580 2023. 08. 01 16:57:45 111 Mágikus intervallum cpp14 Hibás válasz 30/100 159ms 103344 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 2088 KiB
2 Elfogadva 116ms 83940 KiB
subtask2 5/5
3 Elfogadva 3ms 2240 KiB
4 Elfogadva 3ms 2484 KiB
5 Elfogadva 3ms 2664 KiB
6 Elfogadva 3ms 2764 KiB
7 Elfogadva 3ms 3240 KiB
8 Elfogadva 3ms 3276 KiB
subtask3 0/10
9 Elfogadva 3ms 3440 KiB
10 Hibás válasz 3ms 3840 KiB
11 Elfogadva 3ms 3652 KiB
12 Elfogadva 3ms 3656 KiB
13 Elfogadva 3ms 4012 KiB
14 Elfogadva 3ms 4060 KiB
subtask4 10/10
15 Elfogadva 3ms 3828 KiB
16 Elfogadva 2ms 3864 KiB
17 Elfogadva 3ms 4176 KiB
18 Elfogadva 9ms 8832 KiB
19 Elfogadva 130ms 102200 KiB
20 Elfogadva 103ms 102452 KiB
21 Elfogadva 103ms 102756 KiB
subtask5 15/15
22 Elfogadva 2ms 4260 KiB
23 Elfogadva 93ms 90352 KiB
24 Elfogadva 109ms 102784 KiB
subtask6 0/60
25 Elfogadva 118ms 90480 KiB
26 Elfogadva 151ms 102824 KiB
27 Elfogadva 150ms 102864 KiB
28 Elfogadva 140ms 90576 KiB
29 Hibás válasz 153ms 90828 KiB
30 Hibás válasz 136ms 90796 KiB
31 Elfogadva 159ms 103036 KiB
32 Elfogadva 158ms 103080 KiB
33 Elfogadva 115ms 103032 KiB
34 Elfogadva 114ms 103088 KiB
35 Elfogadva 115ms 103032 KiB
36 Elfogadva 149ms 103344 KiB
37 Elfogadva 115ms 103300 KiB
38 Elfogadva 119ms 103300 KiB
39 Elfogadva 3ms 5040 KiB