Submission #917969

#	Time	Username	Problem	Language	Result	Execution time	Memory
917969		406	Stone Arranging 2 (JOI23_ho_t1)	C++17	35 / 100	26 ms	8028 KiB

Main

#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;
}

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