Submission #860139

#	Time	Username	Problem	Language	Result	Execution time	Memory
860139		promitheas	Wall (IOI14_wall)	C++14	0 / 100	111 ms	14048 KiB

wall

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

template<typename T>
T max(T a, T b) {
    return a < b ? b : a;
}
template<typename T>
T min(T a, T b) {
    return a > b ? b : a;
}

template<typename T>
void minset(T& a, T b) {
    a = min(a, b);
}

template<typename T>
void maxset(T& a, T b) {
    a = max(a, b);
}

template<typename T>
void snap(T& a, T l, T h) {
    minset(a, h);
    maxset(a, l);
}

class Node {
public:
    Node* left;
    Node* right;
    bool hasLazy = false;
    int low;
    int high;


    void Propagate() {
        if (!left)left = new Node(this);
        if (!right)right = new Node(this);
        snap(left->low, low, high);
        snap(left->high, low, high);
        snap(right->high, low, high);
        snap(right->high, low, high);
    }
    Node* L() {
        if (!left)left = new Node();
        if (hasLazy) {
            Propagate();
            hasLazy = false;
        }
        return left;
    }
    Node* R() {
        if (!right)right = new Node();
        if (hasLazy) {
            Propagate();
            hasLazy = false;
        }
        return right;
    }

    Node(Node* par) : left{ nullptr }, right{ nullptr }, low{ par->low }, high{ par->high } {}
    Node() : left{ nullptr }, right{ nullptr }, low{ 0 }, high{ 0 } {}
   
    void BuildUp(int l, int r, int tl, int tr, int h) {
        if (l == tl && r == tr) {
            low = max(low, h); //bring lo to at least h
            high = max(high, low); // hi must be at least lo
            hasLazy = true;
            return;
        }
        int mid = (l + r) >> 1;
        if (tr <= mid) {
            return L()->BuildUp(l, mid, tl, tr, h);
        }
        if (tl > mid) {
            return R()->BuildUp(mid + 1, r, tl, tr, h);
        }
        L()->BuildUp(l, mid, tl, mid, h);
        R()->BuildUp(mid + 1, r, mid + 1, tr, h);
    }
    void BreakDown(int l, int r, int tl, int tr, int h) {
        if (l == tl && r == tr) {
            high = min(high, h);
            low = min(low, h);
            hasLazy = true;
            return;
        }
        int mid = (l + r) >> 1;
        if (tr <= mid) {
            return L()->BreakDown(l, mid, tl, tr, h);
        }
        if (tl > mid) {
            return R()->BreakDown(mid + 1, r, tl, tr, h);
        }
        L()->BreakDown(l, mid, tl, mid, h);
        R()->BreakDown(mid + 1, r, mid + 1, tr, h);
    }

    int GetVal(int l, int r, int t) {
        if (l == r)
            return low;
        if (hasLazy) {
            Propagate();
            hasLazy = false;
        }
        int mid = (l + r) >> 1;
        if (t <= mid)
            return L()->GetVal(l, mid, t);
        return R()->GetVal(mid + 1, r, t);
    }
};

Node* node;

int N;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    node = new Node();
    for (int i = 0; i < k; i++) {
        if (op[i] == 1)
            node->BuildUp(0, n - 1, left[i], right[i], height[i]);
        else
            node->BreakDown(0, n - 1, left[i], right[i], height[i]);
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = node->GetVal(0, n - 1, i);
    }
}

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