Submission #1216985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216985		JuanJL	Stone Arranging 2 (JOI23_ho_t1)	C++20	100 / 100	75 ms	21168 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int) x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> iset;

ostream& operator<<(ostream &os, pair<ll,ll> p ){
    return os<<"("<<p.fst<<" "<<p.snd<<")";
}

vector<ll> vals;

ll ind(ll x){
    return lower_bound(ALL(vals),x)-vals.begin();
}

int main(){FIN;
    ll n; cin>>n;
    vector<ll> a(n); forn(i,0,n) cin>>a[i], vals.pb(a[i]);

    sort(ALL(vals));
    vals.erase(unique(ALL(vals)),vals.end());

    forn(i,0,n) a[i]=ind(a[i]);

    //forn(i,0,n) cout<<a[i]<<" "; cout<<'\n';

    vector<vector<ll>> cont(n);
    vector<pair<ll,ll>> s;

    forn(i,0,n){
        if(cont[a[i]].empty()){
            s.pb({i,a[i]});
            cont[a[i]].pb(i);
        }else{
            while(s.back().fst!=cont[a[i]].back()){
                cont[s.back().snd].pop_back();
                s.pop_back();
            }
        }
    }

    vector<ll> col(n);
    forn(i,0,SZ(s)){
        //cout<<s[i]<<'\n';
        forn(j,s[i].fst,(i+1<SZ(s)?s[i+1].fst:n)){
            //cout<<j<<" ";
            col[j]=vals[s[i].snd];
        }
        //cout<<'\n';
    }

    forn(i,0,n) cout<<col[i]<<'\n';
    
    return 0;
}

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