제출 #399378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399378		phathnv	벽 (IOI14_wall)	C++11	100 / 100	810 ms	99280 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

struct Data{
    int lo, hi;
    Data(int _lo = -1e9, int _hi = 1e9){
        lo = _lo;
        hi = _hi;
    }
    Data operator + (const Data &oth){
        if (hi < oth.lo)
            return Data(oth.lo, oth.lo);
        if (oth.hi < lo)
            return Data(oth.hi, oth.hi);
        return Data(max(lo, oth.lo), min(hi, oth.hi));
    }
};

struct SegTree{
    int n;
    vector<Data> d;
    void build(int id, int l, int r){
        if (l == r){
            d[id] = Data(0, 0);
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
    void init(int _n){
        n = _n;
        d.assign(n * 4 + 1, Data(-1e9, 1e9));
        build(1, 1, n);
    }
    void update(int id, int l, int r, int u, int v, Data val){
        if (v < l || r < u)
            return;
        if (u <= l && r <= v){
            d[id] = d[id] + val;
            return;
        }
        d[id << 1] = d[id << 1] + d[id];
        d[id << 1 | 1] = d[id << 1 | 1] + d[id];
        d[id] = Data(-1e9, 1e9);
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
    }
    void solve(int id, int l, int r, int res[]){
        if (l == r){
            assert(d[id].lo == d[id].hi);
            res[l - 1] = d[id].lo;
            return;
        }
        d[id << 1] = d[id << 1] + d[id];
        d[id << 1 | 1] = d[id << 1 | 1] + d[id];
        d[id] = Data(-1e9, 1e9);
        int mid = (l + r) >> 1;
        solve(id << 1, l, mid, res);
        solve(id << 1 | 1, mid + 1, r, res);
    }
    void update(int l, int r, Data val){
        update(1, 1, n, l, r, val);
    }
    void solve(int res[]){
        solve(1, 1, n, res);
    }
} st;

void buildWall(int n, int k, int type[], int l[], int r[], int h[], int res[]){
    st.init(n);
    for(int i = 0; i < k; i++)
        if (type[i] == 1)
            st.update(l[i] + 1, r[i] + 1, Data(h[i], 1e9));
        else
            st.update(l[i] + 1, r[i] + 1, Data(-1e9, h[i]));
    st.solve(res);
    return;
}

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