Submission #1038101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038101		SoulKnight	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	115 ms	23064 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ln '\n'

const int N = 2e5 + 5;
int n, a[N], glit = 1;
vector<int> vec, where[N];

#define lc (v << 1)
#define rc ((v << 1) + 1)

struct node{
    int color;
    int tm = -1;
} seg[4*N];

void pushdown(int v){
    if (!seg[v].color) return;
    seg[rc].color = (seg[rc].tm < seg[v].tm? seg[v].color: seg[rc].color);
    seg[rc].tm = max(seg[rc].tm, seg[v].tm);

    seg[lc].color = (seg[lc].tm < seg[v].tm? seg[v].color: seg[lc].color);
    seg[lc].tm = max(seg[lc].tm, seg[v].tm);

    seg[v].color = 0;
    seg[v].tm = -1;
}

void upd(int v, int tl, int tr, int l, int r, int color){
    if (tr < l || tl > r) return;
    if (l <= tl && tr <= r){
        // cout << v << ' ' << tl << ' ' << tr << ' ' << color << ln;
        seg[v].color = color;
        seg[v].tm = glit;
        return;
    }
    pushdown(v);
    int tm = (tl + tr) / 2;
    upd(lc, tl, tm, l, r, color);
    upd(rc, tm+1, tr, l, r, color);
}

int query(int v, int tl, int tr, int p){
    if (tl == tr) return (seg[v].color == 0? a[tl]: seg[v].color);
    pushdown(v);
    int tm = (tl + tr) / 2;
    if (p <= tm) return query(lc, tl, tm, p);
    else return query(rc, tm+1, tr, p);
}

void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        vec.push_back(a[i]);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for (int i = 1; i <= n; i++){
        a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin()+1;
    }

    for (int i = 1; i <= n; i++){
        // cout << "checking " << i << ' ' << a[i] << ln;
        while (!where[a[i]].empty()){
            int last = where[a[i]].back();
            int actual = query(1, 1, n, last);
            // cout << "looking " << last << ' ' << actual << ln;
            if (actual != a[i]) {where[a[i]].pop_back(); continue;}
            upd(1, 1, n, last, i-1, a[i]);
            break;
        }
        where[a[i]].push_back(i);
        glit++;
    }
    // for (int i = 1; i <= 4*n; i++) pushdown(i);

    for (int i = 1; i <= n; i++){
        int t = query(1, 1, n, i);
        cout << vec[t-1] << ln;
    }




}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // ll TT; cin >> TT;
    // while (TT--) {solve();}

    solve();

}

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