Submission #122673

#	Time	Username	Problem	Language	Result	Execution time	Memory
122673		arman_ferdous	Wall (IOI14_wall)	C++14	100 / 100	767 ms	66956 KiB

wall

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

const int N = 2e6+100;
const int oo = 1e9;

int n;
pair<int,int> t[N<<2];

int getHeight(pair<int,int> v, int init = 0) {
    return max(min(init, v.first), v.second);
}

void add(pair<int,int> &tmp, int h) {
    tmp.second = max(tmp.second, h);
    tmp.first = max(tmp.first, tmp.second);
}
void rem(pair<int,int> &tmp, int h) {
    tmp.first = min(tmp.first, h);
    tmp.second = min(tmp.first, tmp.second);
}

void shift(int node, int L, int R) {
    int lc = node << 1, rc = lc | 1;
    rem(t[lc], t[node].first);
    add(t[lc], t[node].second);
    rem(t[rc], t[node].first);
    add(t[rc], t[node].second);
    t[node] = {oo, 0};
}

void build(int node, int L, int R) {
    t[node] = {oo, 0};
    if(L == R) return;
    int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
    build(lc, L, mid); build(rc, mid + 1, R);
}

void upd(int node, int L, int R, int op, int l, int r, int h) {
    if(r < L || R < l) return;
    if(l <= L && R <= r) {
        if(op == 1) add(t[node], h);
        else rem(t[node], h);
        return;
    } shift(node, L, R);
    int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
    upd(lc, L, mid, op, l, r, h);
    upd(rc, mid + 1, R, op, l, r, h);
}

int soln[N];
void retrieve(int node, int L, int R) {
    if(L == R) return void(soln[L] = getHeight(t[node]));
    shift(node, L, R);
    int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
    retrieve(lc, L, mid); retrieve(rc, mid + 1, R);
}

void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = _n;
    build(1, 0, n - 1);
    for(int i = 0; i < k; i++)
        upd(1, 0, n - 1, op[i], left[i], right[i], height[i]);
    retrieve(1, 0, n - 1);
    for(int i = 0; i < n; i++)
        finalHeight[i] = soln[i];
}

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