Submission #759714

#	Time	Username	Problem	Language	Result	Execution time	Memory
759714		IvanJ	Sequence (APIO23_sequence)	C++17	0 / 100	2028 ms	31564 KiB

sequence

#include "sequence.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 5e5 + 5;

int n, ret = 1;
int num[4];
int a[maxn];

int check(int e, int x) {
	multiset<int> s;
	vector<int> pref(n, 0);
	int flag = 0;
	int hi = 0, cnt = 0, val = 0;
	s.insert(0);
	for(int i = 0;i < n;i++) {
		while(1) {
			if(hi == n) break;
			if(cnt > e) break;
			if(a[hi] == x) cnt++;
			if(a[hi] > x) val++;
			if(a[hi] < x) val--;
			pref[hi] = val;
			if(cnt == e) {
				auto it1 = s.lower_bound(val);
				auto it2 = it1;
				if(it2 != s.begin()) it2--;
				if(abs(*it1 - val) <= e) flag = 1;
				if(abs(*it2 - val) <= e) flag = 1;
			}
			hi++;
		}
		s.insert(pref[i]);
		if(a[i] == x) cnt--;
	}
	return flag;
}

void solve(int x) {
	int lo = 0, hi = num[x], ans = -1;
	while(lo <= hi) {
		int mid = (lo + hi) / 2;
		if(check(mid, x)) ans = mid, lo = mid + 1;
		else hi = mid - 1;
	}
	ret = max(ret, ans);
}

int sequence(int N, vector<int> A) {
	n = N;
	for(int i = 0;i < n;i++) a[i] = A[i], num[a[i]]++;
	int cnt = 1;
	for(int i = 1;i < n;i++) {
		if(a[i] == a[i - 1]) cnt++;
		else cnt = 1;
		ret = max(ret, cnt);
	} 
	
	for(int i = 1;i <= 3;i++) solve(i);
	return ret;
}

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