제출 #541767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541767		starchan	벽 (IOI14_wall)	C++17	100 / 100	1113 ms	144064 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF 1e6
#define zero (int)0
#define MX (int)3e5+5
#define LMX (int)1e7
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
const int mod = 1e9+7; //may fixer to that 99.. number.
struct fixer
{
	int down, up;
};
fixer crate(const int &a, const int &b)
{
	fixer ok;
	ok.down = a;
	ok.up = b;
	assert(a<=b);
	return ok;
}
fixer identity = crate(-INF, INF);
fixer superimpose(const fixer &c1, const fixer &c2)
{
	fixer c3;
	c3.down = max(c1.down, c2.down);
	c3.up = min(c1.up, c2.up);
	if(c3.up >= c3.down)
		return c3;
	if(c3.down == c2.down)
		return crate(c1.up, c1.up);
	else
		return crate(c1.down, c1.down);
}
struct segment_tree
{
	vector<int> tree;
	vector<fixer> lazy;
	void init()
	{
		tree.assign(LMX, 0);
		lazy.assign(LMX, identity);
		return;
	}
	void apply(int id, fixer c)
	{
		if(tree[id] <= c.down)
			tree[id] = c.down;
		if(tree[id] >= c.up)
			tree[id] = c.up;
		lazy[id] = superimpose(c, lazy[id]);
		return;
	}
	void push(int id)
	{
		apply(2*id, lazy[id]);
		apply(2*id+1, lazy[id]);
		lazy[id] = identity;
		return;
	}
	void upd(fixer place, int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return;
		if(ql <= l && r <= qr)
		{
			apply(id, place);
			return;
		}
		int m = (l+r)/2;
		push(id);
		upd(place, ql, qr, 2*id, l, m);
		upd(place, ql, qr, 2*id+1, m+1, r);
		return;
	}
	int val(int pos, int id, int l, int r)
	{
		int m = (l+r)/2;
		if(l==r)
			return tree[id];
		push(id);
		if(pos <= m)
			return val(pos, 2*id, l, m);
		else
			return val(pos, 2*id+1, m+1, r);
	}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	segment_tree work;
	work.init();
	for(int i = 0; i < k; i++)
	{
		if(op[i] == 1)
			work.upd(crate(height[i], INF), left[i], right[i], 1, 0, n-1);
		else
			work.upd(crate(-INF, height[i]), left[i], right[i], 1, 0, n-1);
	}
	for(int i = 0; i < n; i++)
		finalHeight[i] = work.val(i, 1, 0, n-1);
	return;
}

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