oj.uz

Submission #1003548

# Submission time Handle Problem Language Result Execution time Memory
1003548 2024-06-20T12:46:05 Z ProtonDecay314 Wall (IOI14_wall) C++17
100 / 100
 780 ms 224628 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 6 ms 1628 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 4 ms 1628 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 87 ms 13864 KB Output is correct
3 Correct 124 ms 9296 KB Output is correct
4 Correct 389 ms 27752 KB Output is correct
5 Correct 209 ms 28696 KB Output is correct
6 Correct 196 ms 27128 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 7 ms 1628 KB Output is correct
5 Correct 8 ms 1620 KB Output is correct
6 Correct 5 ms 1408 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 82 ms 13888 KB Output is correct
9 Correct 140 ms 9300 KB Output is correct
10 Correct 445 ms 27632 KB Output is correct
11 Correct 245 ms 28756 KB Output is correct
12 Correct 183 ms 27184 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 103 ms 13904 KB Output is correct
15 Correct 30 ms 3152 KB Output is correct
16 Correct 559 ms 28136 KB Output is correct
17 Correct 210 ms 27296 KB Output is correct
18 Correct 237 ms 27500 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1628 KB Output is correct
5 Correct 5 ms 1476 KB Output is correct
6 Correct 5 ms 1628 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 84 ms 13916 KB Output is correct
9 Correct 128 ms 9068 KB Output is correct
10 Correct 465 ms 27728 KB Output is correct
11 Correct 193 ms 28696 KB Output is correct
12 Correct 189 ms 27216 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 93 ms 13916 KB Output is correct
15 Correct 30 ms 3164 KB Output is correct
16 Correct 568 ms 27984 KB Output is correct
17 Correct 202 ms 27476 KB Output is correct
18 Correct 205 ms 27320 KB Output is correct
19 Correct 780 ms 224504 KB Output is correct
20 Correct 771 ms 222040 KB Output is correct
21 Correct 760 ms 224584 KB Output is correct
22 Correct 716 ms 222196 KB Output is correct
23 Correct 694 ms 222200 KB Output is correct
24 Correct 770 ms 221992 KB Output is correct
25 Correct 708 ms 222184 KB Output is correct
26 Correct 759 ms 218420 KB Output is correct
27 Correct 730 ms 224628 KB Output is correct
28 Correct 716 ms 221972 KB Output is correct
29 Correct 700 ms 222200 KB Output is correct
30 Correct 721 ms 222036 KB Output is correct