Submission #768179

#	Time	Username	Problem	Language	Result	Execution time	Memory
768179		green_gold_dog	Sequence (APIO23_sequence)	C++17	35 / 100	1174 ms	74568 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

ll sequence(ll n, vector<ll> a) {
	if (n <= 2000) {
		ll ans = 1;
		for (ll i = 0; i < n; i++) {
			unordered_map<ll, ll> col;
			multiset<ll> now1, now2;
			now2.insert(a[i]);
			col[a[i]]++;
			for (ll j = i + 1; j < n; j++) {
				if (a[j] <= *now2.begin()) {
					now1.insert(a[j]);
				} else {
					now2.insert(a[j]);
				}
				col[a[j]]++;
				while (now1.size() < now2.size()) {
					now1.insert(*now2.begin());
					now2.erase(now2.begin());
				}
				while (now1.size() > now2.size()) {
					now2.insert(*now1.rbegin());
					now1.erase(now1.find(*now1.rbegin()));
				}
				if (ans < col[*now2.begin()]) {
					ans = col[*now2.begin()];
				}
				if (now1.size() == now2.size()) {
					if (ans < col[*now1.rbegin()]) {
						ans = col[*now1.rbegin()];
					}
				}
			}
		}
		return ans;
	} else {
		ll ans = 1;
		ll lst = -1, c = 0;
		for (auto i : a) {
			if (i == lst) {
				c++;
			} else {
				if (ans < c) {
					ans = c;
				}
				lst = i;
				c = 1;
			}
		}
		if (ans < c) {
			ans = c;
		}
		map<ll, ll> col, fir, last;
		for (ll i = 0; i < n; i++) {
			col[a[i]]++;
			last[a[i]] = i;
		}
		for (ll i = n - 1; i >= 0; i--) {
			fir[a[i]] = i;
		}
		for (auto i : a) {
			ll cb = last[i] - fir[i] + 1 - col[i];
			ll cm = n - cb - col[i];
			if (cm + col[i] >= cb) {
				if (ans < col[i]) {
					ans = col[i];
				}
			}
		}
		return ans;
	}
}

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