제출 #1147699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147699		brianhdzmdo	벽 (IOI14_wall)	C++20	100 / 100	704 ms	214236 KiB

wall

#include <algorithm>
#include <cmath>
#include <iostream>
#include <math.h>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include <climits>

#define all(a) (a).begin(), (a).end()
#define allr(a) (a).rbegin(), (a).rend()
#define ll long long
#define fr(i, a, b) for (ll i = a; i < b; i++)
#define fr1(i, a, b) for (ll i = a - 1; i >= b; i--)
#define fi first
#define se second
#define mp(j, k) make_pair(j, k)
#define pb(x) push_back(x)
#define pbp(x, y) push_back({x, y})
#define in(x) insert(x)
#define vec vector<ll>
#define vecv vector<vector<ll> >
#define veb vector<bool>
#define vecp vector<pair<ll,ll>>
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define ac 1e-7
#define fauto(a)   \
  for (auto i : a) \
    cout << i << " ";
#define fautop(a)  \
  for (auto i : a) \
    cout << i.fi << " " << i.se << endl;

using namespace std;

struct Node
{
    int l, r; 
    int mn, mx;
    bool lazyS;
    int lazy;
};

static vector<Node> ST;

void build(int node, int l, int r)
{
    ST[node].l = l;
    ST[node].r = r;
    ST[node].mn = 0;
    ST[node].mx = 0;
    ST[node].lazy = 0;
    ST[node].lazyS = true;

    if(l == r) return;

    int mid = (l + r) / 2;
    int left = node * 2;
    int right = node * 2 + 1;

    build(left, l, mid);
    build(right, mid + 1, r);
}

void apply(int node, int val)
{
    ST[node].mn = val;
    ST[node].mx = val;
    ST[node].lazy = val;
    ST[node].lazyS = true;
}

void propagate(int node)
{
    if(!ST[node].lazyS) return;
    int left = node * 2;
    int right = node * 2 + 1;

    apply(left, ST[node].lazy);
    apply(right, ST[node].lazy);
    ST[node].lazyS = false;
}

void pull(int node)
{
    int left = node * 2;
    int right = node * 2 + 1;
    
    ST[node].mn = min(ST[left].mn, ST[right].mn);
    ST[node].mx = max(ST[left].mx, ST[right].mx);
}

void updateMax(int node, int a, int b, int h)
{
    int l = ST[node].l, r = ST[node].r;

    if(l > b || r < a) return;

    if(a <= l && r <= b)
    {
        if(ST[node].mx < h)
        {
            apply(node, h);
            return;
        }
        if(ST[node].mn >= h) return;
    }

    if(l == r)
    {
        int newh = max(ST[node].mn, h);
        apply(node, newh);
        return;
    }

    propagate(node);
    int left = node * 2;
    int right = node * 2 + 1;

    updateMax(left, a, b, h);
    updateMax(right, a, b, h);

    pull(node);
}

void updateMin(int node, int a, int b, int h)
{
    int l = ST[node].l, r = ST[node].r;

    if(l > b || r < a) return;

    if(a <= l && r <= b)
    {
        if(ST[node].mn > h)
        {
            apply(node, h);
            return;
        }
        if(ST[node].mx <= h) return;
    }

    if(l == r)
    {
        int newh = min(ST[node].mn, h);
        apply(node, newh);
        return;
    }

    propagate(node);
    int left = node * 2;
    int right = node * 2 + 1;

    updateMin(left, a, b, h);
    updateMin(right, a, b, h);

    pull(node);
}

int query(int node, int pos)
{
    int l = ST[node].l, r = ST[node].r;

    if(l == r) return ST[node].mn;

    propagate(node);
    int mid = (l + r) / 2;
    int left = node * 2;
    int right = node * 2 + 1;

    if(pos <= mid)
    {
    return query(left, pos);
    }
    else
    return query(right, pos);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    ST.clear();
    ST.resize(4 * n + 5);

    build(1, 0, n - 1);
    
    fr(i, 0, k)
    {
        int a = left[i];
        int b = right[i];
        int h = height[i];

        if(op[i] == 1)
        {
            updateMax(1, a, b, h);
        }
        else
        {
            updateMin(1, a, b, h);
        }
    }

    fr(i, 0, n) finalHeight[i] = query(1, i);

}

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