5579 2023. 08. 01 16:33:28 111 Mágikus intervallum cpp14 Hibás válasz 30/100 94ms 17420 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 = s0-1;//min_element(ss.begin() + p[i] + 1, ss.begin() + s0) - ss.begin();
			int e1 = e0+1;//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 = s1-1;//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 = e1+1;//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 1812 KiB
2 Elfogadva 74ms 12252 KiB
subtask2 5/5
3 Elfogadva 3ms 2220 KiB
4 Elfogadva 3ms 2464 KiB
5 Elfogadva 3ms 2644 KiB
6 Elfogadva 3ms 2888 KiB
7 Elfogadva 3ms 2956 KiB
8 Elfogadva 3ms 3092 KiB
subtask3 0/10
9 Elfogadva 3ms 3188 KiB
10 Hibás válasz 3ms 3308 KiB
11 Elfogadva 3ms 3524 KiB
12 Elfogadva 3ms 3744 KiB
13 Elfogadva 3ms 4096 KiB
14 Elfogadva 3ms 4048 KiB
subtask4 10/10
15 Elfogadva 2ms 4012 KiB
16 Elfogadva 3ms 4252 KiB
17 Elfogadva 3ms 4256 KiB
18 Elfogadva 8ms 4992 KiB
19 Elfogadva 79ms 15700 KiB
20 Elfogadva 48ms 15696 KiB
21 Elfogadva 48ms 15696 KiB
subtask5 15/15
22 Elfogadva 2ms 4328 KiB
23 Elfogadva 46ms 14520 KiB
24 Elfogadva 61ms 17420 KiB
subtask6 0/60
25 Elfogadva 74ms 14612 KiB
26 Elfogadva 83ms 16136 KiB
27 Elfogadva 85ms 16040 KiB
28 Hibás válasz 82ms 14872 KiB
29 Hibás válasz 82ms 14640 KiB
30 Hibás válasz 82ms 14880 KiB
31 Hibás válasz 94ms 16260 KiB
32 Hibás válasz 94ms 16332 KiB
33 Elfogadva 56ms 16336 KiB
34 Elfogadva 56ms 16332 KiB
35 Elfogadva 57ms 16456 KiB
36 Elfogadva 79ms 16332 KiB
37 Elfogadva 43ms 16336 KiB
38 Elfogadva 48ms 16336 KiB
39 Elfogadva 3ms 4980 KiB