Submission #146227

#	Time	Username	Problem	Language	Result	Execution time	Memory
146227		Diuven	Wall (IOI14_wall)	C++14	100 / 100	714 ms	69736 KiB

wall

#include "wall.h"

const int HMX = 100001;

inline int _min(int a, int b){ return a<b ? a : b; }
inline int _max(int a, int b){ return a>b ? a : b; }

struct node {
    int up=0, dn=0;
    node(){}
    node(int a, int b): up(a), dn(b) {}
    node operator + (const node& nd) const {
        node res = *this;
        res.up = _max(res.up, nd.up);
        res.dn = _max(res.dn, nd.up);
        res.dn = _min(res.dn, nd.dn);
        return res;
    }
} T[1<<22];

void busy(int v, int s, int e){
    if(s==e) return;
    node &ndl = T[v*2], &ndr = T[v*2+1], &nd = T[v];
    ndl = ndl + nd, ndr = ndr + nd;
    nd.up = 0, nd.dn = HMX;
}

void upt(int v, int s, int e, int l, int r, int op, int h){
    if(l<=s && e<=r){
        T[v] = T[v] + node(op==1 ? h : 0, op==2 ? h : HMX); return;
    }
    busy(v,s,e);
    int m = (s+e)/2;
    if(l<=m) upt(v*2,s,m,l,r,op,h);
    if(m<r) upt(v*2+1,m+1,e,l,r,op,h);
}

void get(int v, int s, int e, int ans[]){
    busy(v,s,e);
    if(s==e){ ans[s] = _min(_max(0, T[v].up), T[v].dn); return; }
    get(v*2, s, (s+e)/2, ans);
    get(v*2+1, (s+e)/2+1, e, ans);
}

void buildWall(int n, int k, int op[], int L[], int R[], int H[], int ans[]){
    for(int i=0; i<k; i++) upt(1, 0, n-1, L[i], R[i], op[i], H[i]);
    get(1,0,n-1,ans);
    return;
}

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