제출 #1287543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287543		harryleee	벽 (IOI14_wall)	C++20	0 / 100	97 ms	8184 KiB

wall

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

void buildWall(int n, int q, int t[], int left[], int right[], int h[], int a[])
{
    struct SEGMENT_TREE{
        struct node{
            int lo, hi;
            bool inc;
            inline node(){
                lo = -1;
                hi = 1e9;
                inc = false;
            }
        }; vector<node> st;
        SEGMENT_TREE(int n){
            st.resize(4 * n);
        }

        void update_node(int ind, int h, int t, bool b){
            st[ind].inc |= b;
            if (t == 1){
                st[ind].lo = max(st[ind].lo, h);
                if (st[ind].lo > st[ind].hi) st[ind].hi = 1e9;
            }
            else{
                st[ind].hi = min(st[ind].hi, h);
                if (st[ind].hi < st[ind].lo) st[ind].lo = -1;
            }
            return;
        }

        void update(int ind, int l, int r, int lb, int rb, int h, int t){
            if (l >= lb && r <= rb){
                update_node(ind, h, t, (t == 1));
                return;
            }
            if (st[ind].lo != -1)
                update_node(ind << 1, st[ind].lo, 1, true), update_node(ind << 1 | 1, st[ind].lo, 1, true);
            if (st[ind].hi != -1)
                update_node(ind << 1, st[ind].hi, 2, st[ind].inc), update_node(ind << 1 | 1, st[ind].hi, 2, st[ind].inc);
            st[ind] = node();
            int mid = (l + r) >> 1;
            if (mid >= lb) update(ind << 1, l, mid, lb, rb, h, t);
            if (mid < rb) update(ind << 1 | 1, mid + 1, r, lb, rb, h, t);
            return;
        }

        int get(int ind, int l, int r, int pos){
            if (l == r){
                int res = 0;
                if (res < st[ind].lo) res = st[ind].lo;
                else if (res > st[ind].hi) res = st[ind].hi;
                if (st[ind].lo == -1 && st[ind].hi != 1e9 && st[ind].inc) res = st[ind].hi;
                return res;
            }
            if (st[ind].lo != -1)
                update_node(ind << 1, st[ind].lo, 1, true), update_node(ind << 1 | 1, st[ind].lo, 1, true);
            if (st[ind].hi != -1)
                update_node(ind << 1, st[ind].hi, 2, st[ind].inc), update_node(ind << 1 | 1, st[ind].hi, 2, st[ind].inc);
            st[ind] = node();
            int mid = (l + r) >> 1;
            if (pos >= mid) return (ind << 1, l, mid, pos);
            else return (ind << 1 | 1, mid + 1, r, pos);
        }
    } seg(n);
    for (int i = 0; i < q; ++i)
        seg.update(1, 0, n - 1, left[i], right[i], h[i], t[i]);
    for (int i = 0; i < n; ++i) a[i] = seg.get(1, 0, n -1 , i);
    return;
}

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