제출 #466682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
466682		jli12345	벽 (IOI14_wall)	C++14	100 / 100	1614 ms	69688 KiB

wall

#include <wall.h>
#include <bits/stdc++.h>
using namespace std;

pair<int, int> st[8000100];

pair<int, int> combine(pair<int, int> orig, pair<int, int> upd){
    if (upd.second > orig.first){
        return {upd.second, upd.second};
    } else if (upd.first < orig.second){
        return {upd.first, upd.first};
    } else {
        return {min(orig.first, upd.first), max(orig.second, upd.second)};
    }
}

void pushdown(int node){
    st[node*2] = combine(st[node*2], st[node]);
    st[node*2+1] = combine(st[node*2+1], st[node]);
}

void U(int node, int l, int r, int tl, int tr, pair<int, int> upd){
    if (l >tr || r < tl)
        return;
    if (l >= tl && r <= tr){
        st[node] = combine(st[node], upd);
        //cout << l << " " << r << " " << st[node].first << " " << st[node].second << "\n";
        return;
    }
    pushdown(node);
    int mid = (l+r)/2;
    U(node*2, l, mid, tl, tr, upd);
    U(node*2+1, mid+1, r, tl, tr, upd);
    st[node].first = max(st[node*2].first, st[node*2+1].first);
    st[node].second = min(st[node*2].second, st[node*2+1].second);
}

int Q(int node, int l, int r, int ind){
    if (l > ind || r < ind){
        return 0;
    }
    if (l == r){
        return st[node].first;
    }
    pushdown(node);
    int mid = (l+r)/2;
    st[node].first = max(st[node*2].first, st[node*2+1].first);
    st[node].second = min(st[node*2].second, st[node*2+1].second);
    return max(Q(node*2, l, mid, ind), Q(node*2+1, mid+1, r, ind));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < k; i++){
        if (op[i] == 1){
            U(1, 0, n-1, left[i], right[i], {0x3f3f3f3f, height[i]});
        } else {
            U(1, 0, n-1, left[i], right[i], {height[i], 0});
        }
    }
    for (int i = 0; i < n; i++){
        finalHeight[i] = Q(1, 0, n-1, i);
    }
}

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