| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 851937 | mychecksedad | Sequence (APIO23_sequence) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
a1 -= 2 * k;
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;
}
}
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);
}
while(l <= r){
int m = l+r>>1;
if(check(m)){
ans = m;
l = m + 1;
}else{
r = m - 1;
}
}
return ans;
}