제출 #831095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831095		jasmin	벽 (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;

pair<int,int> zero={0, INF};
struct segtree{
    vector<pair<int,int> > tree;
    vector<pair<int,int> > lazy;

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

    pair<int,int> add_update(pair<int,int> a, pair<int,int> b){

        a.first = max(a.first, b.first);
        a.second = max(a.second, b.first);

        a.second = min(a.second, b.second);

        return a;
    }

    void update_node(int l, int r, int v, pair<int,int> val){

        tree[v] = add_update(tree[v], val);
        lazy[v] = add_update(lazy[v], val);
    }

    void propagate(int l, int r, int v){
        if(lazy[v]==zero) 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]=zero;
    }

    void update_range(int l, int r, int v, int ql, int qr, pair<int,int> 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);
    }

    pair<int,int> 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++){

        pair<int,int> 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.first, val.second);
    }
}

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