# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
759703 |
2023-06-16T15:32:56 Z |
IvanJ |
Sequence (APIO23_sequence) |
C++17 |
|
2000 ms |
31580 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 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 = n, 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];
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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Execution timed out |
2050 ms |
31564 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2069 ms |
31580 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |