Submission #895928

#	Time	Username	Problem	Language	Result	Execution time	Memory
895928		frostray8653	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	147 ms	143396 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int, int>;
#define IO ios::sync_with_stdio(0), cin.tie(0)
#define FOR(p, a, b) for (int p = a; p <= b; p++)
void dbg() {;}
template<class T, class ...U>
void dbg(T a, U ...b) {cout << a << (sizeof...(b) ? ", " : " "); dbg(b...);}
void ent() {cout << "\n";}
/// ---- INITIAL END ----

const int N = 200005;
int a[N];
vector<int> id;
deque<int> pos[N];
int get_id(int x) {
    return lower_bound(id.begin(), id.end(), x) - id.begin();
}

signed main() {
    IO;
    int n;
    cin >> n;
    FOR (i, 1, n) {
        cin >> a[i];
        id.push_back(a[i]);
    }
    sort(id.begin(), id.end());
    id.resize(unique(id.begin(), id.end()) - id.begin());
    
    deque<pii> dq;
    FOR (i, 1, n) {
        int x = get_id(a[i]);
        if (! pos[x].empty()) {
            int lst = pos[x].back();
            while (! dq.empty() && dq.back().first > lst) {
                pos[dq.back().second].pop_back();
                dq.pop_back();
            }
        } else {
            pos[x].push_back(i);
            dq.push_back({i, x});
        }
    }
    int now = 1, now_col = -1;
    for (pii p : dq) {
        for (; now < p.first; now++)
            cout << now_col << "\n";
        now_col = id[p.second];
    }
    for (; now <= n; now++)
        cout << id[dq.back().second] << "\n";

    return 0;
}

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