Submission #1166239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166239		Syrius	Stone Arranging 2 (JOI23_ho_t1)	C++20	100 / 100	199 ms	32160 KiB

Main

#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < int , int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)
typedef vector < int > vint;

const int inf = 1e9 + 9;
const int mxn = 2e5 + 2;
const int mod = 1e9 + 7;

int a[mxn] , pre[mxn];

struct node {

    int tl , tm , tr;
    int val;
    node *left , *right;

    node (int l , int r) {
        tl = l , tr = r , tm = (l + r) / 2;
        val = -1;
        if (l == r) return;
        left = new node(tl , tm);
        right = new node(tm+1 , tr);
    }

    void pro() {
        if (val == -1) return;
        left -> val = right -> val = val;
    }

    void update (int l , int r , int x) {
        if (tl == l && tr == r) {
            val = x;
            return;
        }
        pro();
        if (r <= tm) left -> update(l , r , x);
        else if (l > tm) right -> update(l , r , x);
        else {
            left -> update(l , tm , x);
            right -> update(tm+1 , r , x);
        }
    }

    int get(int p) {
        if (tl == tr) return val;
        pro();
        if (p <= tm) return left -> get(p);
        return right -> get(p);
    }

    void print() {
        if (tl == tr) {
            if (val == -1) cout << a[tl] << ' ';
            else cout << val << ' ';
            return;
        }
        pro();
        left -> print();
        right -> print();
    }
};

int main() {

    int n;
    cin >> n;

    map < int , int > mp;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    node *root = new node(1 , n);

    for (int i = 1; i <= n; i++) {
        int x = mp[a[i]];
        while (root -> get(x) != -1 && x > 0) {
            x = pre[x];
            mp[a[i]] = x;
        }
        pre[i] = mp[a[i]];
        if (pre[i] == 0) {
            mp[a[i]] = i;
            continue;
        }
        root -> update(pre[i] + 1 , i , a[i]);
    }

    root -> print();

}

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