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>
#define NMAX 100005
using namespace std;
int n, v[NMAX], lst[NMAX], fr[2*NMAX], med, ans[2*NMAX], N;
int sL[8*NMAX], sR[8*NMAX], LL[8*NMAX], LR[8*NMAX];
set<int> S;
vector<int> mn[2*NMAX];
void propag(int s[], int lz[], int nod){
s[nod * 2] += lz[nod];
s[nod * 2 + 1] += lz[nod];
lz[nod * 2] += lz[nod];
lz[nod * 2 + 1] += lz[nod];
lz[nod] = 0;
}
void add(int s[], int lz[], int l, int r, int val, int st = 1, int dr = N, int nod = 1){
if (l <= st && dr <= r){
lz[nod] += val;
s[nod] += val;
return;
}
propag(s, lz, nod);
int mid = (st + dr) / 2;
if (l<=mid) add(s, lz, l, r, val, st, mid, nod*2);
if (mid+1<=r) add(s, lz, l, r, val, mid+1, dr, nod*2+1);
s[nod] = min(s[nod*2], s[nod*2+1]);
}
int queryL(int st = 1, int dr = N, int nod = 1){
if (st == dr){
if (sL[nod] > 0) return st;
return st + 1;
}
propag(sL, LL, nod);
int mid = (st + dr) / 2;
if (sL[nod*2+1] > 0)
return queryL(st, mid, nod * 2);
return queryL(mid+1, dr, nod * 2 + 1);
}
int queryR(int st = 1, int dr = N, int nod = 1){
if (st == dr){
if (sR[nod] > 0) return st;
return st - 1;
}
propag(sR, LR, nod);
int mid = (st + dr) / 2;
if (sR[nod*2] > 0)
return queryR(mid+1, dr, nod * 2 + 1);
return queryR(st, mid, nod * 2);
}
int popLeft(){
int x = queryL();
x = *S.lower_bound(x);
S.erase(x);
add(sL, LL, x, 2 * n - 1, -1);
add(sR, LR, 1, x, -1);
return x;
}
int popRight(){
int x = queryR();
x = *prev(S.upper_bound(x));
S.erase(x);
add(sL, LL, x, 2 * n - 1, -1);
add(sR, LR, 1, x, -1);
return x;
}
void readAndPre(){
cin >> n;
for (int i=1;i<=2*n-1;i++){
if (fr[i] == 0) S.insert(i);
mn[i].push_back(0);
}
for (int i=1;i<=n;i++){
cin >> v[i];
S.erase(v[i]);
fr[v[i]]++;
if (i!=n) mn[v[i]].push_back(i);
}
for (int i=n;i>=1;i--){
fr[v[i]]--;
if (fr[v[i]] == 0){
lst[i] = 1;
}
}
med = n;
N = 1;
while (N < 2*n-1) N *= 2;
N = 2*n-1;
for (int i=1;i<=2*n-1;i++){
add(sL, LL, i, i, i-mn[i].back());
add(sR, LR, i, i, 2*n-i-mn[i].back());
}
for (int i=2*n;i<=N;i++){
add(sL, LL, i, i, 1e9);
add(sR, LR, i, i, 1e9);
}
}
int main()
{
readAndPre();
if (lst[n]) S.insert(v[n]);
for (int i=n-1;i>=1;i--){
int a,b;
if (v[i] == v[i+1]){
a = popLeft();
b = popRight();
}
else if (v[i] < v[i+1]){
a = popRight();
b = popRight();
}
else{
a = popLeft();
b = popLeft();
}
ans[2*i+1] = a;
ans[2*i] = b;
if (lst[i])
S.insert(v[i]);
a = mn[v[i]].back();
b = mn[v[i]][mn[v[i]].size() - 2];
add(sL, LL, v[i], v[i], a - b);
add(sR, LR, v[i], v[i], a - b);
mn[v[i]].pop_back();
}
ans[1] = v[1];
for (int i=1;i<=2*n-1;i++) cout << ans[i] << ' ';
return 0;
}
/*
5
1 5 5 5 5
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |