Submission #976333

#	Time	Username	Problem	Language	Result	Execution time	Memory
976333		MinaRagy06	Sequence (APIO23_sequence)	C++17	28 / 100	2056 ms	37880 KiB

sequence

#include <bits/stdc++.h>
#include "sequence.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()

const int inf = 1e9;
int sequence(int n, vector<int> a) {
	vector<int> gud[n + 1];
	for (int i = 0; i <= n; i++) {
		gud[i].push_back(-1);
	}
	for (int i = 0; i < n; i++) {
		gud[a[i]].push_back(i);
	}
	for (int i = 0; i <= n; i++) {
		gud[i].push_back(n);
	}
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		int suf[n + 1]{};
		for (int j = n - 1; j >= 0; j--) {
			suf[j] = suf[j + 1] + (a[j] < i? -1 : 0) + (a[j] > i? 1 : 0);
		}
		array<int, 2> vl[SZ(gud[i]) - 1];
		for (int j = 1; j < SZ(gud[i]) - 1; j++) {
			vl[j] = {inf, -inf};
			for (int k = gud[i][j - 1] + 1; k <= gud[i][j]; k++) {
				vl[j][0] = min(vl[j][0], suf[k]);
				vl[j][1] = max(vl[j][1], suf[k]);
			}
		}
		for (int r = SZ(gud[i]) - 2; r >= 1; r--) {
			array<int, 2> vr = {inf, -inf};
			for (int k = gud[i][r] + 1; k <= gud[i][r + 1]; k++) {
				vr[0] = min(vr[0], suf[k]);
				vr[1] = max(vr[1], suf[k]);
			}
			for (int l = 1; l <= r; l++) {
				if (vr[0] <= vl[l][0]) {
					if (vl[l][0] + l <= r + vr[1] + 1) {
						ans = max(ans, r - l + 1);
						break;
					}
				} else {
					if (l - vl[l][1] <= r - vr[0] + 1) {
						ans = max(ans, r - l + 1);
					}
				}
			}
		}
	}
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18