oj.uz

Submission #759714

# Submission time Handle Problem Language Result Execution time Memory
759714 2023-06-16T15:48:44 Z IvanJ Sequence (APIO23_sequence) C++17
0 / 100
 2000 ms 31564 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 2028 ms 31564 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 8368 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -