| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1184883 | duyngadocton | Sequence (APIO23_sequence) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define task "sequence"
#include "sequence.h"
using namespace std;
#define ii pair<int,int>
#define iii pair<ii,int>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ll long long
const int MAX = (int) 5e5;
const int inf = (int) 1e9;
int n, a[MAX + 5];
vector<int> pos[MAX + 5];
struct node {
int u, v, l, r;
node (int u = 0, int v = 0, int l = 0, int r = 0) : u(u), v(v), l(l), r(r) {}
} info[MAX + 5];
void maximize(int &x, int a) {
if(a > x) x = a;
}
void minimize(int &x, int a) {
if(a < x) x = a;
}
struct stmax {
int st[MAX * 4 + 5];
int lz[MAX * 4 + 5];
void init() {
for(int i = 1; i <= 4 * n; ++i) {
lz[i] = 0;
st[i] = -inf;
}
}
void fix(int id, int l, int r) {
st[id] += lz[id];
if(l != r) {
lz[id * 2] += lz[id];
lz[id * 2 + 1] += lz[id];
}
lz[id] = 0;
}
void upd(int id, int l, int r, int u, int v, int val) {
fix(id, l, r);
if(l > v || r < u) return;
if(u <= l && r <= v) {
lz[id] += val;
fix(id, l, r);
return ;
}
int mid = l + r >> 1;
upd(id * 2, l, mid, u, v, val);
upd(id * 2 + 1, mid + 1, r, u, v, val);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int get(int id, int l, int r, int u, int v) {
fix(id, l, r);int sequence(int N, std::vector<int> A) {
return 0;
}
if(l > v || r < u) return -inf;
if(u <= l && r <= v) return st[id];
int mid = l + r >> 1;
return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
} stmax;
struct stmin {
int st[MAX * 4 + 5], lz[MAX * 4 + 5];
void init() {
for(int i = 1; i <= 4 * n; ++i) {
lz[i] = 0;
st[i] = inf;
}
}
void fix(int id, int l, int r) {
st[id] += lz[id];
if(l != r) {
lz[id * 2] += lz[id];
lz[id * 2 + 1] += lz[id];
}
lz[id] = 0;
}
void upd(int id, int l, int r, int u, int v, int val) {
fix(id, l, r);
if(l > v || r < u) return;
if(u <= l && r <= v) {
lz[id] += val;
fix(id, l, r);
return ;
}
int mid = l + r >> 1;
upd(id * 2, l, mid, u, v, val);
upd(id * 2 + 1, mid + 1, r, u, v, val);
st[id] = min(st[id * 2], st[id * 2 + 1]);
}
int get(int id, int l, int r, int u, int v) {
if(l > v || r < u) return inf;
if(u <= l && r <= v) return st[id];
int mid = l + r >> 1;
return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
} stmin;
bool f(int x) {
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < (int) pos[i].size(); ++j) {
int k = j + x - 1;
if(k < (int) pos[i].size()) {
int L = info[pos[i][k]].l - info[pos[i][j]].v;
int R = info[pos[i][k]].r - info[pos[i][j]].u;
L = max(-x, L);
R = min(R, x);
if(L <= R) return true;
}
}
}
return false;
}
void build() {
stmin.init();
stmax.init();
for(int i = 1; i <= n; ++i) pos[a[i]].pb(i);
for(int i = 1; i <= n; ++i) stmax.upd(1, 1, n, i, n, 1), stmin.upd(1, 1, n, i, n, 1);
for(int i = 1; i <= n; ++i) {
for(int j : pos[i]) {
stmax.upd(1, 0, n, j, n, -1);
stmin.upd(1, 0, n, j, n, -1);
}
int cur = 0;
for(int j = 0; j < (int) pos[i].size(); ++j) {
info[pos[i][j]].u = stmin.get(1, 0, n, cur, pos[i][j] - 1);
info[pos[i][j]].v = stmax.get(1, 0, n, cur, pos[i][j] - 1);
cur = pos[i][j];
}
for(int j = pos[i].size() - 1; j >= 0; --j) {
int x = pos[i][j];
info[x].l = stmin.get(1, 0, n, x, n);
stmin.upd(1, 0, n, x, n, -1);
}
for(int j = pos[i].size() - 1; j >= 0; --j) {
int x = pos[i][j];
info[x].r = stmax.get(1, 0, n, x, n);
stmax.upd(1, 0, n, x, n, 1);
}
for(int j : pos[i]) stmax.upd(1, 0, n, j, n, -2);
}
}
int binary() {
int lo = 0, hi = n+1;
while(hi - lo > 1) {
int mid = lo + hi >> 1;
if(f(mid)) lo = mid;
else hi = mid;
}
return lo;
}
int sequence(int N, vector<int> A) {
n = N;
for(int i = 1; i <= n; ++i) a[i] = A[i - 1];
build();
return binary();
}
//int main() {
// if(fopen(task".inp","r")) {
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
// ios::sync_with_stdio(0);
// cin.tie(NULL);cout.tie(NULL);
// cin >> n;
// for(int i = 1; i <= n; ++i)
// cin >> a[i];
// build();
// cout << binary();
//}