55792023-08-01 16:33:28111Mágikus intervallumcpp14Hibás válasz 30/10094ms17420 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Elfogadva74ms12252 KiB
subtask25/5
3Elfogadva3ms2220 KiB
4Elfogadva3ms2464 KiB
5Elfogadva3ms2644 KiB
6Elfogadva3ms2888 KiB
7Elfogadva3ms2956 KiB
8Elfogadva3ms3092 KiB
subtask30/10
9Elfogadva3ms3188 KiB
10Hibás válasz3ms3308 KiB
11Elfogadva3ms3524 KiB
12Elfogadva3ms3744 KiB
13Elfogadva3ms4096 KiB
14Elfogadva3ms4048 KiB
subtask410/10
15Elfogadva2ms4012 KiB
16Elfogadva3ms4252 KiB
17Elfogadva3ms4256 KiB
18Elfogadva8ms4992 KiB
19Elfogadva79ms15700 KiB
20Elfogadva48ms15696 KiB
21Elfogadva48ms15696 KiB
subtask515/15
22Elfogadva2ms4328 KiB
23Elfogadva46ms14520 KiB
24Elfogadva61ms17420 KiB
subtask60/60
25Elfogadva74ms14612 KiB
26Elfogadva83ms16136 KiB
27Elfogadva85ms16040 KiB
28Hibás válasz82ms14872 KiB
29Hibás válasz82ms14640 KiB
30Hibás válasz82ms14880 KiB
31Hibás válasz94ms16260 KiB
32Hibás válasz94ms16332 KiB
33Elfogadva56ms16336 KiB
34Elfogadva56ms16332 KiB
35Elfogadva57ms16456 KiB
36Elfogadva79ms16332 KiB
37Elfogadva43ms16336 KiB
38Elfogadva48ms16336 KiB
39Elfogadva3ms4980 KiB