Submission #915644

#	Time	Username	Problem	Language	Result	Execution time	Memory
915644		berr	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	158 ms	34220 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 1e9+7;

struct dsu{
    int n;
    vector<int> p;

    dsu(int _n){
        n = _n;
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    int find(int x){
        if(p[x]==x) return x;
        return p[x] = find(p[x]);
    }

    void merge(int x, int y){
        x= find(x); y = find(y);
        if(x==y) return;
        if(x>y) swap(x, y);
        p[y] = x;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
 
    int n; cin >> n;
    vector<int> a(n), t;

    map<int, int> mp;

    for(auto &i: a) cin >> i;

    for(int i=0; i<n; i++){
        if(!mp.count(a[i])){
            mp[a[i]] = t.size(); 
            t.push_back(a[i]);
        }
        a[i] = mp[a[i]];
    }

    dsu d(n);
    vector<vector<int>> g(t.size()+1);

    vector<int> s;

    for(int i=0; i<n; i++){

        if(g[a[i]].size()==0){
            s.push_back(i);

            g[a[i]].push_back(i);
        }
        else{
            while(s.size()&&s.back() > g[a[i]].back()){
                g[a[d.find(s.back())]].pop_back();

                d.merge(g[a[i]].back(), s.back());
                s.pop_back();
            }
            g[a[i]].push_back(i);
            s.push_back(i);
        }
    }

    for(int i=0; i<n; i++) cout<<t[a[d.find(i)]]<<"\n";


}

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