제출 #530160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530160		Hanksburger	벽 (IOI14_wall)	C++17	100 / 100	545 ms	77476 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int lazyMax[8000005], lazyMin[8000005];
vector<int> vec;
void build(int i, int l, int r)
{
	lazyMax[i]=-1;
	lazyMin[i]=-1;
	if (l==r)
		return;
	int mid=(l+r)/2;
	build(i*2, l, mid);
	build(i*2+1, mid+1, r);
}
void push(int i, int op, int h)
{
	if (op==1)
	{
		if (lazyMax[i]!=-1)
			lazyMax[i]=max(lazyMax[i], h);
		else
			lazyMax[i]=h;
		if (lazyMin[i]!=-1)
			lazyMin[i]=max(lazyMin[i], h);
	}
	else
	{
		if (lazyMax[i]!=-1)
		lazyMax[i]=min(lazyMax[i], h);
		if (lazyMin[i]!=-1)
			lazyMin[i]=min(lazyMin[i], h);
		else
			lazyMin[i]=h;
	}
}
void update(int i, int l, int r, int op, int ql, int qr, int h)
{
//	cout << "update " << i << ' ' << l << ' ' << r << ' ' << op << ' ' << ql << ' ' << qr << ' ' << h << '\n';
	if (ql<=l && r<=qr)
	{
//		cout << "updated: " << l << "-" << r << " from " << lazyMax[i] << ' ' << lazyMin[i] << " to ";
		push(i, op, h);
//		cout << lazyMax[i] << " " << lazyMin[i] << '\n';
		return;
	}
//	cout << "push " << lazyMax[i] << " and " << lazyMin[i] << " into [" << l << "-" << (l+r)/2 << "] and [" << (l+r)/2+1 << "-" << r << "]" << '\n';
	if (lazyMax[i]!=-1)
	{
		push(i*2, 1, lazyMax[i]);
		push(i*2+1, 1, lazyMax[i]);
		lazyMax[i]=-1;
	}
	if (lazyMin[i]!=-1)
	{
		push(i*2, 2, lazyMin[i]);
		push(i*2+1, 2, lazyMin[i]);
		lazyMin[i]=-1;
	}
	int mid=(l+r)/2;
	if (l<=qr && ql<=mid)
		update(i*2, l, mid, op, ql, qr, h);
	if (mid+1<=qr && ql<=r)
		update(i*2+1, mid+1, r, op, ql, qr, h);
}
void query(int i, int l, int r)
{
//	cout << "query " << i << ' ' << l << ' ' << r << '\n';
	if (l==r)
	{
		vec.push_back(max(0, lazyMax[i]));
		return;
	}
//	cout << "push " << lazyMax[i] << " and " << lazyMin[i] << " into [" << l << "-" << (l+r)/2 << "] and [" << (l+r)/2+1 << "-" << r << "]" << '\n';
	if (lazyMax[i]!=-1)
	{
		push(i*2, 1, lazyMax[i]);
		push(i*2+1, 1, lazyMax[i]);
		lazyMax[i]=-1;
	}
	if (lazyMin[i]!=-1)
	{
		push(i*2, 2, lazyMin[i]);
		push(i*2+1, 2, lazyMin[i]);
		lazyMin[i]=-1;
	}
	int mid=(l+r)/2;
	query(i*2, l, mid);
	query(i*2+1, mid+1, r);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[])
{
	build(1, 0, n-1);
	for (int i=0; i<k; i++)
//	{
		update(1, 0, n-1, op[i], l[i], r[i], h[i]);
//		query(1, 0, n-1);
//		cout << "vec: ";
//		for (int j=0; j<n; j++)
//			cout << vec[j] << ' ';
//		cout << '\n';
//		vec.clear();
//	}
	query(1, 0, n-1);
	for (int i=0; i<n; i++)
		fh[i]=vec[i];
}

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