Submission #774641

#	Time	Username	Problem	Language	Result	Execution time	Memory
774641		vjudge1	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	108 ms	35212 KiB

Main

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n;
int a[maxn];
vector<int> poi;
vector<int> pos[maxn];
int k[maxn];
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        poi.pb(a[i]);
    }
    sort(poi.begin(), poi.end());
    poi.resize(distance(poi.begin(), unique(poi.begin(), poi.end())));
    vector<int> vt;
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(poi.begin(), poi.end(), a[i]) - poi.begin();
        if (pos[a[i]].size())
        {
            int p = pos[a[i]].back();
            while (vt.size() && vt.back() >= p)
            {
                pos[a[vt.back()]].pop_back();
                vt.pop_back();
            }
        }
        vt.pb(i);
        pos[a[i]].pb(i);
    }
    int l = 1;
    for (int i = 0; i < vt.size(); i++)
    {
        for (int j = l; j <= vt[i]; j++)
        {
            k[j] = a[vt[i]];
        }
        l = vt[i] + 1;
    }
    for (int i = 1; i <= n; i++)
    {
        cout << poi[k[i]] << " ";
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < vt.size(); i++)
      |                     ~~^~~~~~~~~~~

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