Submission #1281751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281751		ghammazhassan	Stone Arranging 2 (JOI23_ho_t1)	C++20	100 / 100	239 ms	40164 KiB

Main

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define int long long
#define endl "\n"
#define fi first
#define se second
const int M=1e9+7;
const int inf = 1e9;
const int LOG=20;
const int N=2e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;

void solve()
{       
    cin >> n;
    vector<int>a(n+1);
    map<int,int>d;
    map<int,int>d2;
    int j=1;
    for (int i=1;i<=n;i++){
        cin >> a[i];
        if (!d[a[i]]){
            d[a[i]]=j++;
        }
        d2[d[a[i]]]=a[i];
        a[i]=d[a[i]];
    }
    vector<vector<int>>cn(n+1);
    vector<pair<int,int>>o;
    o.push_back({0,0});
    for (int i=1;i<=n;i++){
        x=a[i];
        while (cn[x].size()){
            y=cn[x].back();
            int l=0;
            int h=o.size()-1;
            int m=(l+h)/2;
            while (l<h){
                if (y>=o[m].fi){
                    l=m;
                }
                else{
                    h=m-1;
                }
                m=(l+h+1)/2;
            }
            if (y>o[m].se or a[o[m].se]==x)break;
            cn[x].pop_back();
        }
        if (cn[x].size()){
            y=cn[x].back();
            while (o.back().fi>y){
                o.pop_back();
            }
            o.push_back({y,i});
            // cout << x << " " << y << " " << i << endl;
        }
        cn[x].push_back(i);
    }
    for (auto i:o){
        for (int j=i.fi;j<=i.se;j++){
            a[j]=a[i.se];
        }
    }
    for (int i=1;i<=n;i++){
        cout << d2[a[i]] << endl;
    }

}
signed main()    
{

    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed << setprecision(9);
    srand(time(0));
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
        solve();
        q++;
    }
} 

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