Submission #798844

#	Time	Username	Problem	Language	Result	Execution time	Memory
798844		vjudge1	Stone Arranging 2 (JOI23_ho_t1)	C++17	60 / 100	2079 ms	21104 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);
}

int find(int val, int r, node *x) {
    if(val < x->mn || x->mx < val || r <= x->l) {
        return r;
    }
    if(x->l + 1 == x->r) {
        return x->l;
    }
    push(x);
    int res = find(val, r, x->right);
    if(res == r) {
        res = find(val, r, x->left);
    }
    return res;
}

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);
    for(int i = 0; i < n; ++ i) {
        cin >> m;
        update(find(m, i, root), 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:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main() {
      | ^~~~

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