제출 #1085099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1085099		BLOBVISGOD	벽 (IOI14_wall)	C++17	100 / 100	520 ms	67400 KiB

wall

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int oo = 1e9;

struct segtree{
    struct node{
        int lo=-oo, hi=oo;
        void operator+=(node b){
            if (b.hi <= lo) lo=b.hi,hi=b.hi;
            else if (b.lo >= hi) hi = b.lo, lo = b.lo;
            else lo = max(lo,b.lo), hi = min(hi,b.hi);
        }
    };
    int n;
    vector<node> seg;

    segtree(int N){
        n = 1;
        while(n<N) n*= 2;
        seg.resize(n*2);
    }

    void push(int id){
        seg[id*2] += seg[id];
        seg[id*2+1] += seg[id];
        seg[id] = {};
    }

    void upd(int id, int l, int r, int ql, int qr, node u){
        if (l >= qr or r <= ql) return;
        if (l >= ql and r <= qr) return void(seg[id] += u);
        int mid = (l+r)/2;
        push(id);
        upd(id*2,l,mid,ql,qr,u);
        upd(id*2+1,mid,r,ql,qr,u);
    }

    void update(int l, int r, node u){
        upd(1,0,n,l,r,u);
    }

    node& operator[](int id){
        return seg[id+n];
    }

    void finish(){
        rep(i,1,n) push(i);
    }
};

void buildWall(int n, int k, int* op, int* L, int* R, int* H, int* fh){
    cin.tie(NULL),cin.sync_with_stdio(false);

    segtree seg(n);
    rep(i,0,k){
        int  t = op[i], l = L[i], r = R[i], h = H[i];
        if (t==1) seg.update(l,r+1,{h,oo});
        else seg.update(l,r+1,{-oo,h});
    }

    seg.finish();

    vi sol(n);
    rep(i,0,n){
        sol[i] = max(sol[i],seg[i].lo);
        sol[i] = min(sol[i],seg[i].hi);
    }

    rep(i,0,n) fh[i] = sol[i];

}

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