Submission #917975

#	Time	Username	Problem	Language	Result	Execution time	Memory
917975		406	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	72 ms	8528 KiB

Main

#include <bits/stdc++.h>
#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)) {
                                assert(r > 0);
                                dsu::merge(r, i);
                        }
                }
                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;
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40