Submission #1043484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043484		deera	Wall (IOI14_wall)	C++14	100 / 100	520 ms	89116 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;
#define cint const int
 
class Tree {
    public :
        cint N;
        vector<pair<int, int>> tree;

        Tree(cint &n) : N(n) {
            tree.resize(4 * n, {0, INT_MAX});
        }
 
        void push(cint &x, cint &l, cint &r) {
            if(l == r) {
                return;
            }

            int _l = x * 2;
            int _r = x * 2 + 1;
 
            laze(_l, 1, tree[x].first);
            laze(_l, 2, tree[x].second);
            laze(_r, 1, tree[x].first);
            laze(_r, 2, tree[x].second);

            tree[x] = {0, INT_MAX};
        }
        
        void laze(cint &x, cint &op, cint &v) {
            if(op == 1) {
                tree[x].first = max(tree[x].first, v);
                tree[x].second = max(tree[x].second, tree[x].first);
            } else {
                tree[x].second = min(tree[x].second, v);
                tree[x].first = min(tree[x].first, tree[x].second);
            }
        }
 
        void update(cint &x, cint &l, cint &r, cint &a, cint &b, cint &op, cint &v) {
            if(r < a || b < l) return;
            if(a <= l && r <= b) {
                laze(x, op, v);
            } else {
                push(x, l, r);
                int m = (l + r) / 2;
                update(x * 2, l, m, a, b, op, v);
                update(x * 2 + 1, m + 1, r, a, b, op, v);
            }
        }
 
        void output(cint &x, cint &l, cint &r, int results[]) {
            if(l == r) {
                results[l] = tree[x].first;
                return;
            }
 
            push(x, l, r);
            int m = (l + r) / 2;
            output(x * 2, l, m, results);
            output(x * 2 + 1, m + 1, r, results);
        }
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    Tree tree(n);
    for(int i = 0; i < k; i++) {
        tree.update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
    }
 
    tree.output(1, 0, n - 1, finalHeight);
}

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