| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 749446 | penguin133 | 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 <bits/stdc++.h>
using namespace std;
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node{
int s, e, m;
int mx, mn, lazy, val;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
if(s != e)l = new node(s, m), r = new node(m+1, e);
mx = mn = lazy = val = 0;
}
void prop(){
if(!lazy)return;
mx += lazy, mn += lazy;
if(s != e)l->lazy += lazy, r->lazy += lazy;
lazy = 0;
}
void upd(int a, int b, int c){
if(a == s && b == e)lazy += c;
else{
if(b <= m)l->upd(a, b, c);
else if(a > m)r->upd(a, b, c);
else l->upd(a, m, c), r->upd(m+1, b, c);
l->prop(), r->prop();
mn= min(l->mn, r->mn);
mx= max(l->mx, r->mx);
}
}
pi qry(int a, int b){
prop();
if(a == s && b == e)return {mn, mx};
if(b <= m)return l->qry(a, b);
else if(a > m)return r->qry(a, b);
else{
pi lft = l->qry(a, m), rgt = r->qry(m+1 ,b);
return {min(lft.fi, rgt.fi), max(lft.se, rgt.se)};
}
}
}*lft, *rgt, *lft2, *rgt2;
vector <int> occ[500005];
int sequence(int N, vector <int> A){
for(int i=0;i<N;i++)occ[A[i]].push_back(i);
lft = new node(0, N);
rgt = new node(0, N);
lft2 = new node(0, N - 1);
rgt2 = new node(0, N - 1);
int ans = 1;
for(int i=0;i<N;i++){
lft->upd(i, N - 1, 1);
rgt->upd(0, i, 1);
lft2->upd(i, N - 1, 1);
rgt2->upd(0, i, 1);
}
bool f = 0;
for(int i=1;i<=N;i++){
for(auto j : occ[i]){
lft2->upd(j, N - 1, -2);
rgt2->upd(0, j, -2);
}
int in = 0;
for(int j = 1; j < (int)occ[i].size(); j++){
int r = occ[i][j];
while(in < j){
int l = occ[i][in];
pi tmp = rgt->qry(0, l), tmp2 = lft->qry(r, N - 1);
pi ref = rgt->qry(l, l), ref2 = lft->qry(r, r);
pi tmp3 = rgt2->qry(0, l), tmp4 = lft2->qry(r, N - 1);
pi ref3 = rgt2->qry(l, l), ref4 = lft2->qry(r, r);
tmp.fi -= ref.fi; tmp.se -= ref.se; tmp2.fi -= ref2.fi; tmp2.se -= ref2.se;
tmp.fi += tmp2.fi;
tmp.se += tmp2.se;
tmp3.fi -= ref3.fi; tmp3.se -= ref3.se; tmp4.fi -= ref4.fi; tmp4.se -= ref4.se;
tmp3.fi += tmp4.fi;
tmp3.se += tmp4.se;
int val = lft->qry(r - 1, r - 1).fi - lft->qry(l, l).fi;
int val2 = lft2->qry(r - 1, r - 1).fi - lft2->qry(l, l).fi;
long long mn = val + tmp.se, mx = val2 + tmp3.fi;
if(mn * mx > 0)in++;
else break;
}
ans = max(ans, j - in + 1);
//if(mid == 3)cout << val << ' ' << mx << ' ' << mn << '\n';
}
for(auto j : occ[i]){
lft->upd(j, N - 1, -2);
rgt->upd(0, j, -2);
}
}
return ans;
}
int main() {
int N;
assert(1 == scanf("%d", &N));
std::vector<int> A(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &A[i]));
}
int result = sequence(N, A);
printf("%d\n", result);
return 0;
}