This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#ifdef ONLINE_JUDGE
// #include "cyberland.h"
//#endif
#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 2e5 + 2;
const ll Mod = 998244353;
const int szBL = 50;
const int INF = 1e9 + 7;
const int BASE = 137;
int n;
int a[N], c[N];
set<pair<int,int>> sIT[N];
vector<int> zip;
void compress() {
rep (i, 1, n) zip.push_back(a[i]);
sort (ALL(zip));
zip.resize(unique(ALL(zip)) - zip.begin());
rep (i ,1, n) {
a[i] = lower_bound(ALL(zip), a[i]) - zip.begin();
}
}
void solution() {
cin >> n;
rep (i, 1, n) {
cin >> a[i];
}
compress();
set<pair<int, int>> IT;
rep (i, 1, n) {
if (sIT[a[i]].empty()) sIT[a[i]].insert(mp(i, i)), IT.insert(mp(i, i));
else {
pair<int,int> lstIT = *prev(sIT[a[i]].end());
auto it = IT.lower_bound(lstIT);
static vector<pair<int,int>> vecdel; vecdel.clear();
for (auto it = IT.lower_bound(lstIT); it != IT.end(); ++it) {
pair<int,int> curIT = *it;
int curcol = a[curIT.se];
sIT[curcol].erase(sIT[curcol].find(curIT));
vecdel.push_back(curIT);
}
iter (&itv, vecdel) IT.erase(IT.find(itv));
IT.insert(mp(lstIT.fs, i));
sIT[a[i]].insert(mp(lstIT.fs, i));
}
}
rep (i ,1, n) {
auto it = IT.upper_bound(mp(i, INF));
--it;
cout << zip[a[it->se]] <<" ";
}
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// file ("PAINT");
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
7
1 2 3 1 2 1 3
1
4 4 30
3
1 1 2 1
0 1 5
0 2 5
1 3 2
2 3 4
3 2
0 1 5
0 2 5
1
1 2
*/
Compilation message (stderr)
Main.cpp: In function 'void solution()':
Main.cpp:54:18: warning: variable 'it' set but not used [-Wunused-but-set-variable]
54 | auto it = IT.lower_bound(lstIT);
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |