Submission #798849

#	Time	Username	Problem	Language	Result	Execution time	Memory
798849		vjudge1	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	475 ms	165112 KiB

Main

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

struct node {
    int l, r, mn = 1e9 + 1, mx = 0, lazy = 0;
    node *left = NULL, *right = NULL;

    node(int l, int r):l(l), r(r) {}
};

void push(node *x) {
    if(x->left == NULL) {
        x->left = new node(x->l, (x->l + x->r) / 2);
    }
    if(x->right == NULL) {
        x->right = new node((x->l + x->r) / 2, x->r);
    }
    if(x->lazy == 0) {
        return;
    }
    x->left->mn  = x->left->mx  = x->left->lazy  = 
    x->right->mn = x->right->mn = x->right->lazy = x->lazy;
    x->lazy = 0;
}

void update(int l, int r, int val, node *x) {
    if(r <= x->l || x->r <= l) {
        return;
    }
    if(l <= x->l && x->r <= r) {
        x->mn = x->mx = x->lazy = val;
        return;
    }
    push(x);
    update(l, r, val, x->left);
    update(l, r, val, x->right);
    x->mn = min(x->left->mn, x->right->mn);
    x->mx = max(x->left->mx, x->right->mx);
}

bool check(int val, int pos, node *x) {
    if(val < x->mn || x->mx < val) {
        return false;
    }
    if(x->mn == val || x->mx == val) {
        return true;
    }
    push(x);
    return pos < x->left->r ? 
        check(val, pos, x->left)  :
        check(val, pos, x->right) ;
}

void print(int pos, node *x) {
    if(pos <= x->l) {
        return;
    }
    if(x->l + 1 == x->r) {
        cout << x->mn << '\n';
        return;
    }
    push(x);
    print(pos, x->left);
    print(pos, x->right);
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, k = 1;
    for(cin >> n; k < n; k <<= 1);
    node *root = new node(0, k);
    map < int, stack < int > > mp;
    for(int i = 0; i < n; ++ i) {
        cin >> m;
        auto it = mp.find(m);
        if(it == mp.end()) {
            mp[m];
            it = mp.find(m);
        }
        int pos = i;
        for(; !it->second.empty() && pos == i; it->second.pop()) {
            if(check(m, it->second.top(), root)) {
                pos = it->second.top();
            }
        }
        it->second.push(i);
        update(pos, i + 1, m, root);
    }
    print(n, root);
} 

Compilation message (stderr)

Main.cpp: In function 'void push(node*)':
Main.cpp:30:18: warning: operation on 'x->node::right->node::mn' may be undefined [-Wsequence-point]
   30 |     x->right->mn = x->right->mn = x->right->lazy = x->lazy;
      |     ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main() {
      | ^~~~

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