제출 #917972

#제출 시각아이디문제언어결과실행 시간메모리
917972406Stone Arranging 2 (JOI23_ho_t1)C++17
35 / 100
2058 ms8796 KiB
#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], 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) cin >> a[i]; copy(a, a + n, A); sort(A, A + n); FOR(i, 0, n) a[i] = lower_bound(A, A + n, a[i]) - A + 1; FOR(i, 0, n) { #define a a[i] 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 << A[dsu::col[dsu::gpr(i)] - 1] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...