Submission #1266909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266909		ngocphu	벽 (IOI14_wall)	C++20	100 / 100	771 ms	89052 KiB

wall

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const long long INF = 2000000000000000000LL;
const int maxN = 2e6 + 4;
const int LOG = 18;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
const int MOD = 1e9 + 7;
const int base = 311;
int n, k, op[maxN], le[maxN], ri[maxN], height[maxN], final_height[maxN];

struct dataa
{
    int min_val, max_val;

    dataa()
    {
        min_val = 0;
        max_val = 1e9;
    }
    dataa(int a, int b)
    {
        min_val = a;
        max_val = b;
    }
};

dataa st[4 * maxN];

void apply(int id, dataa x)
{
    st[id].min_val = max(st[id].min_val, x.min_val);
    st[id].max_val = max(st[id].max_val, st[id].min_val);
    st[id].max_val = min(st[id].max_val, x.max_val);
    st[id].min_val = min(st[id].min_val, st[id].max_val);
}

void push(int id)
{
    apply(id * 2, st[id]);
    apply(id * 2 + 1, st[id]);
    st[id] = dataa(0, 1e9);
}

void update(int id, int l, int r, int u, int v, dataa x)
{
    if (l > v || r < u) return;

    if (l >= u && r <= v) apply(id, x);
    else
    {
        push(id);

        int m = (l + r) / 2;

        update(id * 2, l, m, u, v, x);
        update(id * 2 + 1, m + 1, r, u, v, x);
    }
}

dataa get(int id, int l, int r, int idx)
{
    if (l == r)
    {
        return st[id];
    }
    else
    {
        push(id);
        int m = (l + r) / 2;

        if (idx <= m) return get(id * 2, l, m, idx);
        else return get(id * 2 + 1, m + 1, r, idx);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int final_height[]) {
	for (int i = 0; i < k; i++)
    {
		if (op[i] == 1) update(1, 1, n, left[i] + 1, right[i] + 1, dataa(height[i], 1e9));
        else update(1, 1, n, left[i] + 1, right[i] + 1, dataa(0, height[i]));
	}
	for (int i = 0; i < n; i++) final_height[i] = get(1, 1, n, i + 1).min_val;
}

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