Submission #931672

#	Time	Username	Problem	Language	Result	Execution time	Memory
931672		Yazan_Alattar	Stone Arranging 2 (JOI23_ho_t1)	C++14	100 / 100	111 ms	21752 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 500007;
const ll inf = 1e9;
const ll INF = 1e12;
const ll mod = 1e9 + 7;
const double eps = 1e-6;

map <int,int> last;
int n, p[M], sz[M], col[M], Right[M], Prev[M];

int root(int x){
    while(p[x] != x){
        p[x] = p[p[x]];
        x = p[x];
    }
    return x;
}

void connect(int x, int y){
    x = root(x); y = root(y);
    if(x == y) return;

    if(sz[x] > sz[y]) swap(x, y);
    p[x] = y;
    sz[y] += sz[x];
    Right[y] = max(Right[y], Right[x]);
    return;
}

void solve(int _){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int x; cin >> x;

        p[i] = i; sz[i] = 1; col[i] = x; Right[i] = i;

        int j = last[x];
        while(j > 0){
            if(col[root(j)] != x)
                j = Prev[j];
            else break;
        }
        Prev[i] = j;
        last[x] = i;


        if(j > 0){
            int r = Right[root(j)];

            while(r < i){
                connect(r, r + 1);
                r = Right[root(r)];
            }

        }
        col[root(i)] = x;
    }

    for(int i = 1; i <= n; ++i) cout << col[root(i)] << endl;
    return;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; ++i) solve(t);

    return 0;
}

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