Submission #1003548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003548		ProtonDecay314	Wall (IOI14_wall)	C++17	100 / 100	780 ms	224628 KiB

wall

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;

class Tree {
    public:
        int mn, mx; // These are also the lazy parameters
        bool marked_min, marked_max;
        int l, r;
        Tree* lt;
        Tree* rt;

        Tree(int a_l, int a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), marked_min(false), marked_max(false) {};

        void push() {
            if(!marked_min && !marked_max) return;
            if(l == r) {
                marked_min = marked_max = false;
                return;
            }

            if(marked_min) {
                if(lt->mn < mn && mn < lt->mx) {
                    lt->mn = mn;
                }
                if(mn >= lt->mx) {
                    lt->mn = lt->mx = mn;
                    lt->marked_max = true; // ! TODO rethink this
                }

                lt->marked_min = true;

                if(rt->mn < mn && mn < rt->mx) {
                    rt->mn = mn;
                }
                if(mn >= rt->mx) {
                    rt->mn = rt->mx = mn;
                    rt->marked_max = true;
                }

                rt->marked_min = true;

                marked_min = false;
            }

            if(marked_max) {
                if(lt->mn < mx && mx < lt->mx) {
                    lt->mx = mx;
                }
                if(mx <= lt->mn) {
                    lt->mn = lt->mx = mx;
                    lt->marked_min = true;
                }

                lt->marked_max = true;

                if(rt->mn < mx && mx < rt->mx) {
                    rt->mx = mx;
                }
                if(mx <= rt->mn) {
                    rt->mn = rt->mx = mx;
                    rt->marked_min = true;
                }

                rt->marked_max = true;

                marked_max = false;
            }
        }

        void combine() {
            mn = min(lt->mn, rt->mn);
            mx = max(lt->mx, rt->mx);
        }

        void build() {
            if(l == r) return;

            int m = (l + r) >> 1;

            lt = new Tree(l, m);
            rt = new Tree(m + 1, r);

            lt->build();
            rt->build();

            // I'd normally combine but there's no need to here :))
            // Everything is zero, anyways
        }

        void set_min(int ql, int qr, int nmn) {
            if(ql > r || qr < l) return;

            push();
            if(ql == l && qr == r) {
                if(mn < nmn && nmn < mx) {
                    marked_min = true;
                    mn = nmn;
                }

                if(nmn >= mx) {
                    marked_min = true;
                    marked_max = true;
                    mn = mx = nmn;
                }
                push();
                return;
            }

            int m = (l + r) >> 1;

            lt->set_min(ql, min(qr, m), nmn);
            rt->set_min(max(m + 1, ql), qr, nmn);

            combine();
        }

        void set_max(int ql, int qr, int nmx) {
            if(ql > r || qr < l) return;

            push();
            if(ql == l && qr == r) {
                if(mn < nmx && nmx < mx) {
                    marked_max = true;
                    mx = nmx; // ! Ahahah, you were doing mn = nmx, be careful!
                }

                if(nmx <= mn) {
                    marked_min = true;
                    marked_max = true;
                    mn = mx = nmx;
                }
                push();
                return;
            }

            int m = (l + r) >> 1;

            lt->set_max(ql, min(qr, m), nmx);
            rt->set_max(max(m + 1, ql), qr, nmx);

            combine();
        }

        int query(int i) {
            push();

            if(l == r && r == i) {
                assert(mn == mx);
                return mn;
            }

            int m = (l + r) >> 1;

            if(i <= m) return lt->query(i);
            else return rt->query(i);
        }
};

// IOI Function Signatures
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    Tree tr(0, n - 1);
    tr.build();

    for(int i = 0; i < k; i++) {
        if(op[i] == 1) {
            // Add (set min)
            tr.set_min(left[i], right[i], height[i]);
        } else {
            // Remove (set max)
            tr.set_max(left[i], right[i], height[i]);
        }
    }

    for(int i = 0; i < n; i++) {
        finalHeight[i] = tr.query(i);
    }
};

Compilation message (stderr)

wall.cpp: In constructor 'Tree::Tree(int, int)':
wall.cpp:13:15: warning: 'Tree::rt' will be initialized after [-Wreorder]
   13 |         Tree* rt;
      |               ^~
wall.cpp:9:13: warning:   'int Tree::mn' [-Wreorder]
    9 |         int mn, mx; // These are also the lazy parameters
      |             ^~
wall.cpp:15:9: warning:   when initialized here [-Wreorder]
   15 |         Tree(int a_l, int a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), marked_min(false), marked_max(false) {};
      |         ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39