#ifdef ONLINE_JUDGE
#include "cyberland.h"
#endif
#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 5e5 + 7;
const int Mod = 1e9 +7;
const int szBL = 50;
const ll INF = 1e18;
const int BASE = 137;
int n;
int a[N];
namespace sub2 {
vector<int> vec;
int numVal;
int cnt[N];
struct fenwick_Tree {
int Range;
int fen[N];
void init (int n) {
Range = n;
rep (i, 1, Range) fen[i] = 0;
}
void update (int pos, int val) {
for (; pos <= Range; pos += pos & -pos) fen[pos] += val;
}
int get (int pos) {
int res = 0;
for (; pos > 0; pos -= pos & -pos) res += fen[pos];
return res;
}
}BIT;
void compress() {
rep (i, 1, n) vec.push_back(a[i]);
sort (ALL(vec));
vec.resize (numVal = unique(ALL(vec)) - vec.begin());
}
int solution() {
compress();
int res = 0;
rep (i, 1, n) {
BIT.init(numVal);
rep (v,1, numVal) cnt[v] = 0;
rep (j, i, n) {
int nval = lower_bound(ALL(vec), a[j]) - vec.begin() + 1;
BIT.update(nval, 1);
int pos1; {
int lf = 1, rt = numVal;
while (lf < rt) {
int mid = lf + rt >> 1;
if (BIT.get(mid) - 1>= floor(1.0 * (j - i) /2)) rt = mid;
else lf = mid + 1;
}
pos1 = lf;
}
int pos2; {
int lf = 1, rt = numVal;
while (lf < rt) {
int mid = lf + rt >> 1;
if (BIT.get(mid) - 1 >= ceil(1.0 * (j - i) /2)) rt = mid;
else lf = mid + 1;
}
pos2 = lf;
}
res = max({res, cnt[pos1], cnt[pos2]});
cnt[a[j]]++;
}
}
return res;
}
}
namespace sub3 {
bool check () {
rep (i, 1, n) if (a[i] > a[i + 1]) {
rep (j, i + 1, n) if (a[j] < a[j + 1]) return 0;
}
return 1;
}
int cnt[N];
int R[N], L[N];
int solution() {
rep (i, 1, n) if (L[a[i]] == 0) L[a[i]] = i;
reb (i, n, 1) if (R[a[i]] == 0) R[a[i]] = i;
int res = 0;
rep (i, 1, n) {
int pos = i;
while (a[i] == a[i + 1]) ++i;
res = max(res, i - pos + 1);
}
rep (i, 1, n) {
int val = a[i];
if (R[val] - L[val] + 1 == cnt[val]) continue;
int smaller = (n - R[val] + L[val] - 1), bigger = R[val] - L[val] + 1 - cnt[val];
if (smaller >= bigger) res = max(res, cnt[val]);
else if (bigger - smaller <= cnt[val]) res = max(res, cnt[val]);
}
return res;
}
}
int sequence (int _n, vector<int> A) {
n = _n;
rep (i, 1, n) a[i] = A[i - 1];
cin >> n;
rep (i, 1, n) cin >> a[i];
if (n <= 3000)
return sub2 :: solution();
else if (sub3 :: check())
return sub3 :: solution();
}
//void solution() {
// cin >> n;
// rep (i, 1, n) cin >> a[i];
// if (n <= 3000)
// cout << sub2 :: solution() <<"\n";
// else
// if (sub3 :: check())
// cout << sub3 :: solution() <<"\n";
//// else cout << sub160907 :: solution() <<"\n";
//}
//
//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
//int main () {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//// file ("c");
// int num_Test = 1;
//// cin >> num_Test;
// while (num_Test--)
// solution();
//}
/*
7
1 2 3 1 2 1 3
1
4 4 30
3
1 1 2 1
0 1 5
0 2 5
1 3 2
2 3 4
3 2
0 1 5
0 2 5
1
1 2
*/
Compilation message
sequence.cpp: In function 'int sub2::solution()':
sequence.cpp:74:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
74 | int mid = lf + rt >> 1;
| ~~~^~~~
sequence.cpp:83:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int mid = lf + rt >> 1;
| ~~~^~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:135:1: warning: control reaches end of non-void function [-Wreturn-type]
135 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
44 ms |
13392 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
13396 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
13400 KB |
Output is correct |
| 2 |
Correct |
44 ms |
13396 KB |
Output is correct |
| 3 |
Incorrect |
53 ms |
13364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
