Submission #831557

#	Time	Username	Problem	Language	Result	Execution time	Memory
831557		hct_2so1	Stone Arranging 2 (JOI23_ho_t1)	C++14	100 / 100	204 ms	30284 KiB

Main

#include <bits/stdc++.h>

#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define F first
#define S second
#define pii(x, y) make_pair(x, y)
#define __builtin_popcount __builtin_popcountll
#define __builtin_ctz __builtin_ctzll
#define __builtin_clz __builtin_clzll
#define lg(x) (63 - __builtin_clz(x))

template <class X, class Y>
    bool minimize(X &x, const Y &y)
    {
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y)
    {
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }

using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int M = 6e5;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll oo = 2e18;
const double eps = 1e-1;

int n, a[N], st[4 * N], lz[4 * N];
vector<int> vi, ar[N];

void Input(void)
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i], vi.push_back(a[i]);
    uni(vi);
    for (int i = 1; i <= n; i ++) a[i] = lower_bound(all(vi), a[i]) - vi.begin() + 1;
}

void update(int u, int v, int vv, int id = 1, int l = 1, int r = n)
{
    if (lz[id])
    {
        st[id] = lz[id];
        if (l < r)
        {
            lz[id * 2] = lz[id];
            lz[id * 2 + 1] = lz[id];
        }
        lz[id] = 0;
    }
    if (r < u || v < l) return ;
    if (u <= l && r <= v)
    {
        st[id] = vv;
        if (l < r)
        {
            lz[id * 2] = vv;
            lz[id * 2 + 1] = vv;
        }
        return ;
    }
    int mid = (l + r) / 2;
    update(u, v, vv, id * 2, l, mid);
    update(u, v, vv, id * 2 + 1, mid + 1, r);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}

int get(int pos, int id = 1, int l = 1, int r = n)
{
    if (lz[id])
    {
        st[id] = lz[id];
        if (l < r)
        {
            lz[id * 2] = lz[id];
            lz[id * 2 + 1] = lz[id];
        }
        lz[id] = 0;
    }
    if (r < pos || pos < l) return 0;
    if (l == r) return st[id];
    int mid = (l + r) / 2;
    return max(get(pos, id * 2, l, mid), get(pos, id * 2 + 1, mid + 1, r));
}

void solve(void)
{
    set<int> st;
    for (int i = 1; i <= n; i ++)
    {
        int L = i;
        if (sz(ar[a[i]])) L = ar[a[i]].back() + 1;
        update(L, i, a[i]);
        while (sz(st))
        {
            auto itr = --st.end();
            int k = a[*itr];
            if (*itr >= L)
            {
                st.erase(itr);
                ar[k].pop_back();
                if (sz(ar[k])) st.insert(ar[k].back());
            }
            else break;
        }
        if (sz(ar[a[i]])) st.erase(ar[a[i]].back());
        ar[a[i]].push_back(i);
        st.insert(i);
    }
    for (int i = 1; i <= n; i ++) cout << vi[get(i) - 1] << '\n';
}

int main()
{
    std::ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("CLASSROOM.inp", "r", stdin);
//    freopen("CLASSROOM.out", "w", stdout);
    int test = 1;
    //cin >> test;
    while (test --)
    {
        Input();
        solve();
    }
    return 0;
}

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