제출 #691707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
691707		ismayil	벽 (IOI14_wall)	C++17	0 / 100	145 ms	8152 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
using namespace std;
const ll INF = 1e18;
struct segtree{
    struct node{
        ll mn, mx;
    };
    vector<node> tree;
    ll size;
    segtree(ll n){
        size = 1;
        while(size < n) size *= 2;
        tree.resize(2 * size - 1, {0, INF});
    }
    void propagate(ll x, ll lx, ll rx){
        tree[2 * x + 1].mn = min(tree[2 * x + 1].mn, tree[x].mn);
        tree[2 * x + 1].mn = max(tree[2 * x + 1].mn, tree[x].mx);
        tree[2 * x + 1].mx = min(tree[2 * x + 1].mx, tree[x].mn);
        tree[2 * x + 1].mx = max(tree[2 * x + 1].mx, tree[x].mx);

        tree[2 * x + 2].mn = min(tree[2 * x + 2].mn, tree[x].mn);
        tree[2 * x + 2].mn = max(tree[2 * x + 2].mn, tree[x].mx);
        tree[2 * x + 2].mx = min(tree[2 * x + 2].mx, tree[x].mn);
        tree[2 * x + 2].mx = max(tree[2 * x + 2].mx, tree[x].mx);

        tree[x].mn = 0;
        tree[x].mx = INF;
    }
    void update(ll op, ll l, ll r, ll h, ll x, ll lx, ll rx){
        if(r <= lx || rx <= l) return;
        if(l <= lx && rx <= r){
            if(op == 1){
                tree[x].mn = max(tree[x].mn, h);
                tree[x].mx = max(tree[x].mx, h);
            }else{
                tree[x].mn = min(tree[x].mn, h);
                tree[x].mx = min(tree[x].mx, h);
            }
            return;
        }
        propagate(x, lx, rx);
        ll mx = (lx + rx) / 2;
        update(op, l, r, h, 2 * x + 1, lx, mx);
        update(op, l, r, h, 2 * x + 2, mx, rx);
    }
    void update(ll op, ll l, ll r, ll h){
        update(op, l, r, h, 0, 0, size);
    }
    ll query(ll pos, ll x, ll lx, ll rx){
        if(rx - lx == 1){
            return tree[x].mn;
        }
        propagate(x, lx, rx);
        ll mx = (lx + rx) / 2;
        if(pos <= mx) return query(pos, 2 * x + 1, lx, mx);
        return query(pos, 2 * x + 2, mx, rx);
    }
    ll query(ll pos){
        return query(pos, 0, 0, size);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    segtree st(n);
    for (int i = 0; i < k; i++) st.update(op[i], left[i], right[i] + 1, height[i]);
    for (int i = 0; i < n; i++) finalHeight[i] = st.query(i);
}

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