Submission #902643

#	Time	Username	Problem	Language	Result	Execution time	Memory
902643		tvladm2009	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	694 ms	36204 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define mp(a, b) make_pair(a, b)

const int N = 2e5 + 7;

pair<int, int> tree[4 * N];
pair<int, int> lazy[4 * N];

void push(int v, int tl, int tr) {
    if (tl < tr) {
        lazy[2 * v] = max(lazy[2 * v], lazy[v]);
        lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]);
    }
    tree[v] = max(tree[v], lazy[v]);
    lazy[v] = mp(0, 0);
}

void update(int v, int tl, int tr, int l, int r, pair<int, int> c) {
    push(v, tl, tr);
    if (l <= tl && tr <= r) {
        lazy[v] = max(lazy[v], c);
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    if (l <= tm) update(2 * v, tl, tm, l, min(r, tm), c);
    if (tm + 1 <= r) update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, c);
    push(2 * v, tl, tm);
    push(2 * v + 1, tm + 1, tr);
    tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}

pair<int, int> query(int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (l <= tl && tr <= r) {
        return tree[v];
    }
    int tm = (tl + tr) / 2;
    if (l <= tm && r <= tm) {
        return query(2 * v, tl, tm, l, r);
    } else if (tm + 1 <= l && tm + 1 <= r) {
        return query(2 * v + 1, tm + 1, tr, l, r);
    } else {
        return max(query(2 * v, tl, tm, l, tm), query(2 * v + 1, tm + 1, tr, tm + 1, r));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<int> v;
    map<int, vector<int>> pos;
    vector<int> nxt(n + 1);
    iota(nxt.begin() + 1, nxt.end(), 0);
    for (int i = 1; i <= n; ++i) {
        if (pos[a[i]].size() == 0) {
            pos[a[i]].push_back(i);
            update(1, 1, n, i, i, mp(i, a[i]));
            continue;
        }
        int l = pos[a[i]].back();
        nxt[i] = l - 1;
        update(1, 1, n, l, i, mp(i, a[i])); 
        for (int j = i - 1; j >= l; j = nxt[j]) {
            if (!pos[a[j]].empty() && pos[a[j]].back() == j) pos[a[j]].pop_back();
        }
        pos[a[i]].push_back(i);
    }
    for (int i = 1; i <= n; ++i) cout << query(1, 1, n, i, i).second << endl;
    return 0;
}

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