Submission #540250

#	Time	Username	Problem	Language	Result	Execution time	Memory
540250		dxz05	Wall (IOI14_wall)	C++14	100 / 100	1179 ms	88992 KiB

wall

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

struct node{
    int mn;
    int mx;
    node(){
        mn = 1e9;
        mx = -1e9;
    }
};

const int N = 2e6 + 3e2;

node t[4 * N];

void chmin(node &var, int val){
    var.mn = min(var.mn, val);
    var.mx = min(var.mx, val);
}

void chmax(node &var, int val){
    var.mn = max(var.mn, val);
    var.mx = max(var.mx, val);
}

void push(int v){
    if (t[v].mn != 1e9){
        chmin(t[v + v], t[v].mn);
        chmin(t[v + v + 1], t[v].mn);
        t[v].mn = 1e9;
    }
    if (t[v].mx != -1e9){
        chmax(t[v + v], t[v].mx);
        chmax(t[v + v + 1], t[v].mx);
        t[v].mx = -1e9;
    }
}

void update(int v, int tl, int tr, int l, int r, int val, char type){
    if (l <= tl && tr <= r){
        if (type == '+'){
            chmax(t[v], val);
        } else {
            chmin(t[v], val);
        }
        return;
    }
    if (tl > r || tr < l) return;
    push(v);
    int tm = (tl + tr) >> 1;

    update(v + v, tl, tm, l, r, val, type);
    update(v + v + 1, tm + 1, tr, l, r, val, type);
}

node get(int v, int tl, int tr, int pos){
    if (tl == tr) return t[v];
    push(v);
    int tm = (tl + tr) >> 1;
    if (pos <= tm) return get(v + v, tl, tm, pos); else
        return get(v + v + 1, tm + 1, tr, pos);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < n; i++){
        update(1, 0, n - 1, i, i, 0, '+');
    }

    for (int i = 0; i < k; i++){
        update(1, 0, n - 1, left[i], right[i], height[i], op[i] == 1 ? '+' : '-');
    }

    for (int i = 0; i < n; i++){
        finalHeight[i] = get(1, 0, n - 1, i).mx;
    }

}

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