Submission #831094

#	Time	Username	Problem	Language	Result	Execution time	Memory
831094		jasmin	Wall (IOI14_wall)	C++17	0 / 100	1 ms	340 KiB

wall

// ioi 14 day 1
#include<bits/stdc++.h>
using namespace std;

const int INF=1e9+7;

struct node{
    int lb=0;
    int ub=INF;
};
node zero={0, INF};

struct todo{
    int lb=0;
    int ub=INF;
};
todo nothing={0, INF};

struct segtree{
    vector<node> tree;
    vector<todo> lazy;

    segtree(int n){
        tree.assign(n*4, zero);
    }

    void update_node(int l, int r, int v, todo val){

        // update tree
        tree[v].lb = max(tree[v].lb, val.lb);
        tree[v].ub = max(tree[v].ub, val.lb);

        tree[v].ub = min(tree[v].ub, val.ub);

        //update lazy
        lazy[v].lb = max(lazy[v].lb, val.lb);
        lazy[v].ub = max(lazy[v].ub, val.lb);

        lazy[v].ub = min(lazy[v].ub, val.ub);
    }

    void propagate(int l, int r, int v){
        if(lazy[v].lb==0 && lazy[v].ub==INF) return;

        int m=l+(r-l)/2;
        update_node(l, m, v*2+1, lazy[v]);
        update_node(m, r, v*2+2, lazy[v]);

        lazy[v]=nothing;
    }

    void update_range(int l, int r, int v, int ql, int qr, todo val){
        if(qr<=l || r<=ql) return;
        if(ql<=l && r<=qr){

            update_node(l, r, v, val);
        }
        propagate(l, r, v);

        int m=l+(r-l)/2;
        update_range(l, m, v*2+1, ql, qr, val);
        update_range(m, r, v*2+2, ql, qr, val);
    }

    node query(int l, int r, int v, int x){
        if(l+1==r){
            return tree[v];
        }
        propagate(l, r, v);

        int m=l+(r-l)/2;
        if(x<m){
            return query(l, m, v*2+1, x);
        }
        return query(m, r, v*2+2, x);
    }

};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    segtree seg(n);
    for(int i=0; i<k; i++){

        todo val;
        if(op[i]==1){ //adding

            val={height[i], INF};
        }
        else{ //removing

            val={0, height[i]};
        }
        seg.update_range(0, n, 0, left[i], right[i]+1, val);
    }


    for(int i=0; i<n; i++){
        auto val = seg.query(0, n, 0, i);

        finalHeight[i] = min(val.lb, val.ub);
    }
}

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