#include<sequence.h>
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 5e5+10;
int n, lazy[4*N];
array<int, 2> T[4*N], zero = {0, 0}; // pos min, pos max, neg min, neg max
vector<int> c[N], arr;
array<int, 2> calc(array<int, 2> &a, array<int, 2> &b){
array<int, 2> res;
res[0] = min(a[0], b[0]);
res[1] = max(a[1], b[1]);
return res;
}
void build(int l, int r, int k){
if(l == r){
T[k][0] = l;
T[k][1] = l;
lazy[k] = 0;
return;
}
int m = l+r>>1;
build(l, m, k<<1);
build(m+1, r, k<<1|1);
lazy[k] = 0;
T[k] = calc(T[k<<1], T[k<<1|1]);
}
void push(int k){
if(lazy[k] != 0){
for(int i = 0; i < 2; ++i) T[k<<1][i] += lazy[k];
for(int i = 0; i < 2; ++i) T[k<<1|1][i] += lazy[k];
lazy[k<<1] += lazy[k];
lazy[k<<1|1] += lazy[k];
lazy[k] = 0;
}
}
void update(int l, int r, int ql, int qr, int k, int delta){
if(ql > r || l > qr) return;
if(ql <= l && r <= qr){
for(int i = 0; i < 2; ++i) T[k][i] += delta;
lazy[k] += delta;
return;
}
push(k);
int m = l+r>>1;
update(l, m, ql, qr, k<<1, delta);
update(m+1, r, ql, qr, k<<1|1, delta);
T[k] = calc(T[k<<1], T[k<<1|1]);
}
array<int, 2> get(int l, int r, int ql, int qr, int k){
if(ql > r || l > qr) return {0, -1};
if(ql <= l && r <= qr){
return T[k];
}
push(k);
int m = l+r>>1;
array<int, 2> a1 = get(l, m, ql, qr, k<<1);
array<int, 2> a2 = get(m+1, r, ql, qr, k<<1|1);
if(a1[0] > a1[1])
return a2;
if(a2[0] > a2[1])
return a1;
return calc(a1, a2);
}
bool check(int k){
vector<int> v;
for(int i = 1; i <= n; ++i) if(c[i].size() >= k) v.pb(i);
sort(all(v));
int last = 1; // last non applied
build(1, n, 1);
for(int x: v){
// cout << k << ' ' << x << '\n';
while(last <= x){
for(auto pos: c[last]){
update(1, n, pos, n, 1, last == x ? -1 : -2);
}
++last;
}
int l, r;
for(int i = 0; i < c[x].size() - k + 1; ++i){
l = c[x][i], r = c[x][i + k - 1];
// cout << k << ' ' << x << ' ' << l << ' ' << r << '\n';
array<int, 2> a1 = get(1, n, r, n, 1);
array<int, 2> a2;
if(l > 1){
array<int, 2> f = get(1, n, 1, l - 1, 1);
a2 = calc(zero, f);
}else
a2 = zero;
// cout << a1[0] << ' ' << a1[1] << ' ' << a2[0] << ' ' << a2[1] << "f\n";
if((a1[0] >= a2[0] && a1[0] <= a2[1]) || (a2[0] >= a1[0] && a2[0] <= a1[1])){
return 1;
}
if(a1[0] < a2[0]){
if(a2[0] - a1[1] <= k) return 1;
}else{
if(a1[0] - a2[1] <= k) return 1;
}
}
for(auto pos: c[x]){
update(1, n, pos, n, 1, -1);
}
}
return 0;
}
int sequence(int _n, vector<int> A){
n = _n;
int ans = 1, l = 2, r = n;
arr = A;
for(int i = 0; i < n; ++i){
c[A[i]].pb(i + 1);
}
vector<int> sz;
for(int i = 1; i <= n; ++i) if(c[i].size() > 0) sz.pb(c[i].size());
sort(all(sz));
for(int i = sz.size() - 1; i >= 0; --i){
if(i == sz.size() - 1 || sz[i] != sz[i + 1]){
if(check(sz[i])) return i;
}
}
return ans;
}
Compilation message
sequence.cpp: In function 'void build(int, int, int)':
sequence.cpp:27:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | int m = l+r>>1;
| ~^~
sequence.cpp: In function 'void update(int, int, int, int, int, int)':
sequence.cpp:53:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int m = l+r>>1;
| ~^~
sequence.cpp: In function 'std::array<int, 2> get(int, int, int, int, int)':
sequence.cpp:66:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | int m = l+r>>1;
| ~^~
sequence.cpp: In function 'bool check(int)':
sequence.cpp:81:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
81 | for(int i = 1; i <= n; ++i) if(c[i].size() >= k) v.pb(i);
| ~~~~~~~~~~~~^~~~
sequence.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0; i < c[x].size() - k + 1; ++i){
| ~~^~~~~~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:136:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | if(i == sz.size() - 1 || sz[i] != sz[i + 1]){
| ~~^~~~~~~~~~~~~~~~
sequence.cpp:127:15: warning: unused variable 'l' [-Wunused-variable]
127 | int ans = 1, l = 2, r = n;
| ^
sequence.cpp:127:22: warning: unused variable 'r' [-Wunused-variable]
127 | int ans = 1, l = 2, r = n;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
80 ms |
44228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
111 ms |
53704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
