제출 #399375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399375		phathnv	Wall (IOI14_wall)	C++11	8 / 100	3067 ms	17700 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;
            cerr << l << ' ' << r << ' ' << d[id].lo << ' ' << d[id].hi << endl;
            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);
    }
    int get(int id, int l, int r, int pos){
        if (pos < l || r < pos)
            return -1e9;
        if (l == r){
            assert(d[id].lo == d[id].hi);
            return d[id].lo;
        }
        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;
        return max(get(id << 1, l, mid, pos), get(id << 1 | 1, mid + 1, r, pos));
    }
    void update(int l, int r, Data val){
        update(1, 1, n, l, r, val);
    }
    int get(int pos){
        return get(1, 1, n, pos);
    }
} 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]));
    for(int i = 0; i < n; i++)
        res[i] = st.get(i + 1);
    return;
}

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