제출 #1150807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150807		buzdi	벽 (IOI14_wall)	C++17	0 / 100	28 ms	63032 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int NMAX = 2e6;
const int INF = 2e9;

struct LazyNode {
    int mini, maxi;
    LazyNode() : mini(0), maxi(INF) {}
    LazyNode(int mini, int maxi) : mini(mini), maxi(maxi) {}
};

struct AINT {
    LazyNode lazy[4 * NMAX + 1];

    void Apply(int node, int left, int right, LazyNode parent_lazy) {
        lazy[node].mini = max(lazy[node].mini, parent_lazy.mini);
        lazy[node].maxi = max(lazy[node].maxi, lazy[node].mini);
        lazy[node].maxi = min(lazy[node].maxi, parent_lazy.maxi);
        lazy[node].mini = min(lazy[node].mini, lazy[node].maxi);
    }

    void Push(int node, int left, int right) {
        int mid = (left + right) / 2;
        Apply(node * 2, left, mid, lazy[node]);
        Apply(node * 2 + 1, mid + 1, right, lazy[node]);
        lazy[node] = LazyNode();
    }

    void Update(int node, int left, int right, int Uleft, int Uright, LazyNode value) {
        if(left > Uright || right < Uleft) {
            return;
        }
        if(left >= Uleft && right <= Uright) {
            Apply(node, left, right, value);
            return;
        }

        Push(node, left, right);
        int mid = (left + right) / 2;
        Update(node * 2, left, mid, Uleft, Uright, value);
        Update(node * 2 + 1, mid + 1, right, Uleft, Uright, value);
    }

    void Print(int node, int left, int right, int* a) {
        if(left == right) {
            a[left] = lazy[node].mini;
            return;
        }

        Push(node, left, right);
        int mid = (left + right) / 2;
        Print(node * 2, left, mid, a);
        Print(node * 2 + 1, mid + 1, right, a);
    }
}aint;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	for(int i = 0; i < k; i++) {
		int type = op[i];
		int l = left[i]; l++;
		int r = right[i]; r++;
		int value = height[i];

        if(type == 1) { // Maximize
            aint.Update(1, 1, n, l, r, LazyNode(value, INF));
        }
        else {
            aint.Update(1, 1, n, l, r, LazyNode(0, value));
        }
	}
	aint.Print(1, 1, n, finalHeight);
}

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