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 int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ar = array<int, 2>;
const int64_t INF = 1ll << 60;
const int N = 2e5 + 5;
namespace dsu {
int dpr[N], col[N], cnt[N];
int gpr(int x) {
return dpr[x] == x ? x : dpr[x] = gpr(dpr[x]);
}
void merge(int L, int R) {
R = gpr(R);
L = gpr(L);
if (L == R) return;
--cnt[col[R]];
dpr[R] = L;
}
}
int n, a[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
iota(dsu::dpr, dsu::dpr + N, 0);
dsu::cnt[0] = N;
cin >> n;
FOR(i, 0, n) {
int a; cin >> a;
if (dsu::cnt[a]) {
for (int r = i - 1; r >= 0 && dsu::col[dsu::gpr(r)] != a; r = dsu::gpr(r - 1))
dsu::merge(i, r);
}
int x = dsu::gpr(i);
--dsu::cnt[dsu::col[x]];
dsu::col[x] = a;
++dsu::cnt[dsu::col[x]];
}
FOR(i, 0, n) cout << dsu::col[dsu::gpr(i)] << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |