55782023-08-01 16:25:19111Mágikus intervallumcpp14Hibás válasz 5/100944ms16116 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 = min_element(ss.begin() + p[i] + 1, ss.begin() + s0) - ss.begin();
			int e1 = 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 = 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 = 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
1Elfogadva3ms1684 KiB
2Elfogadva104ms12120 KiB
subtask25/5
3Elfogadva3ms2144 KiB
4Elfogadva2ms2184 KiB
5Elfogadva3ms2280 KiB
6Elfogadva3ms2364 KiB
7Elfogadva3ms2512 KiB
8Elfogadva3ms2604 KiB
subtask30/10
9Elfogadva3ms2728 KiB
10Hibás válasz3ms2940 KiB
11Elfogadva3ms3020 KiB
12Elfogadva3ms3020 KiB
13Elfogadva4ms3300 KiB
14Elfogadva3ms3504 KiB
subtask40/10
15Elfogadva3ms3680 KiB
16Elfogadva3ms3792 KiB
17Elfogadva7ms3824 KiB
18Elfogadva527ms4564 KiB
19Időlimit túllépés879ms9052 KiB
20Időlimit túllépés865ms8988 KiB
21Időlimit túllépés857ms9116 KiB
subtask50/15
22Elfogadva3ms3984 KiB
23Időlimit túllépés899ms8488 KiB
24Időlimit túllépés899ms10092 KiB
subtask60/60
25Elfogadva107ms14664 KiB
26Elfogadva119ms15916 KiB
27Elfogadva118ms16116 KiB
28Időlimit túllépés861ms8976 KiB
29Időlimit túllépés852ms8980 KiB
30Időlimit túllépés865ms8820 KiB
31Időlimit túllépés870ms9696 KiB
32Időlimit túllépés874ms9512 KiB
33Időlimit túllépés865ms9448 KiB
34Időlimit túllépés857ms9452 KiB
35Időlimit túllépés865ms9448 KiB
36Időlimit túllépés925ms9392 KiB
37Időlimit túllépés944ms9504 KiB
38Időlimit túllépés857ms9456 KiB
39Elfogadva3ms4436 KiB