제출 #532427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532427		sliviu	벽 (IOI14_wall)	C++17	0 / 100	1 ms	332 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

int n, cur = 0;

struct node {
	int omin = 2000000000, omax = 0;
};

vector<node> t;
vector<int> sol;

void Propagate(int node) {
	t[2 * node].omin = max(t[node].omax, min(t[node].omin, t[2 * node].omin));
	t[2 * node].omax = min(t[node].omin, max(t[node].omax, t[2 * node].omax));
	t[2 * node + 1].omin = max(t[node].omax, min(t[node].omin, t[2 * node + 1].omin));
	t[2 * node + 1].omax = min(t[node].omin, max(t[node].omax, t[2 * node + 1].omax));
	t[node].omin = 2000000000, t[node].omax = 0;
}

void Update(int q, int h, int posleft, int posright, int node = 1, int left = 1, int right = n) {
	if (posleft <= left && right <= posright) {
		if (q == 1) {
			t[node].omax = max(t[node].omax, h);
			t[node].omin = max(t[node].omin, t[node].omax);
		}
		else {
			t[node].omin = min(t[node].omin, h);
			t[node].omax = min(t[node].omin, t[node].omax);
		}
		return;
	}
	Propagate(node);
	int m = (left + right) / 2;
	if (posleft <= m)
		Update(q, h, posleft, posright, 2 * node, left, m);
	if (posright > m)
		Update(q, h, posleft, posright, 2 * node + 1, m + 1, right);
}

void Solve(int node = 1, int left = 1, int right = n) {
	if (left == right) {
		sol.emplace_back(min(t[node].omin, t[node].omax));
		return;
	}
	Propagate(node);
	int m = (left + right) / 2;
	Solve(2 * node, left, m);
	Solve(2 * node + 1, m + 1, right);
}

void buildWall(int n, int k, int type[], int l[], int r[], int val[], int ans[]) {
	t = vector<node>(4 * n);
	for (int i = 0; i < k; ++i)
		Update(type[i], val[i], l[i] + 1, r[i] + 1);
	//Solve();
	for (int i = 0; i < n; ++i)
		ans[i] = sol[i];
}

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