Submission #297637

#	Time	Username	Problem	Language	Result	Execution time	Memory
297637		juckter	Wall (IOI14_wall)	C++14	100 / 100	990 ms	224740 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct node {
    int l, r, mx, mn;
    node *left, *right;

    void compose(int _mx, int _mn) {
        if(_mx > mn)
            mn = _mx;
        if(_mn < mx)
            mx = _mn;
        mx = max(mx, _mx);
        mn = min(mn, _mn);
    }

    void push() {
        left->compose(mx, mn);
        right->compose(mx, mn);
        mx = 0;
        mn = INF;
    }

    node(int l, int r) : l(l), r(r), mx(0), mn(INF) {
        if(l < r) {
            int m = (l + r) / 2;
            left = new node(l, m);
            right = new node(m + 1, r);
        }
    }

    void upd(int rl, int rr, int mn, int mx) {
        if(rr < l || r < rl)
            return;
        if(rl <= l && r <= rr) {
            compose(mx, mn);
            return;
        }
        push();
        left->upd(rl, rr, mn, mx);
        right->upd(rl, rr, mn, mx);
    }

    void trav(int* fi) {
        if(l == r)
            fi[l] = mx;
        else {
            push();
            left->trav(fi);
            right->trav(fi);
        }
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    node tree(0, n - 1);
    for(int i = 0; i < k; i++) {
        if(op[i] == 1)
            tree.upd(left[i], right[i], INF, height[i]);
        else
            tree.upd(left[i], right[i], height[i], 0);
    }

    tree.trav(finalHeight);

    return;
}

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