Submission #283105

#	Time	Username	Problem	Language	Result	Execution time	Memory
283105		peijar	Wall (IOI14_wall)	C++17	100 / 100	1048 ms	110456 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

#define SZ(v) ((int)(v).size())
using ll = long long;

const int MAXN = 8e6;

int li[MAXN], ri[MAXN];
int lazyMin[MAXN], lazyMax[MAXN];
int val[MAXN];

void buildTree(int node, int l, int r)
{
	li[node] = l, ri[node] = r;

	lazyMin[node] = 1e9;
	lazyMax[node] = 0;
	if (l == r)
		return ;
	buildTree(2*node+1, l, (l+r)/2);
	buildTree(2*node+2, (l+r)/2+1, r);
}

void changeMax(int node, int v)
{
	lazyMax[node] = max(lazyMax[node], v);
	lazyMin[node] = max(lazyMin[node], v);
}

void changeMin(int node, int v)
{
	lazyMin[node] = min(lazyMin[node], v);
	lazyMax[node] = min(lazyMax[node], v);
}

void push(int node)
{
	if (li[node] == ri[node])
		val[li[node]] = min(lazyMin[node], max(lazyMax[node], val[li[node]]));
	else
	{
		changeMax(2*node+1, lazyMax[node]);
		changeMin(2*node+1, lazyMin[node]);
		changeMin(2*node+2, lazyMin[node]);
		changeMax(2*node+2, lazyMax[node]);
	}
	lazyMin[node] = 1e9;
	lazyMax[node] = 0;
}

void updateMax(int node, int lo, int up, int v)
{
	push(node);
	if (li[node] > up or ri[node] < lo)
		return ;
	if (li[node] >= lo and ri[node] <= up)
	{
		changeMax(node, v);
		return;
	}
	updateMax(2*node+1, lo, up, v);
	updateMax(2*node+2, lo, up, v);
}

void updateMin(int node, int lo, int up, int v)
{
	push(node);
	if (li[node] > up or ri[node] < lo)
		return ;
	if (li[node] >= lo and ri[node] <= up)
	{
		changeMin(node, v);
		return;
	}
	updateMin(2*node+1, lo, up, v);
	updateMin(2*node+2, lo, up, v);
}

void recursivePush(int node)
{
	push(node);
	if (li[node] < ri[node])
	{
		recursivePush(2*node+1);
		recursivePush(2*node+2);
	}
}

void buildWall(int n, int k, int op[], int l[], int r[], int v[], int fh[])
{
	buildTree(0, 0, n-1);
	for (int i(0); i < k; ++i)
	{
		if (op[i] == 1)
			updateMax(0, l[i], r[i], v[i]);
		else
			updateMin(0, l[i], r[i], v[i]);
	}
	recursivePush(0);
	for (int i(0); i < n; ++i)
		fh[i] = val[i];
}
/*
int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbCol, nbRequetes;
	cin >> nbCol >> nbRequetes;
	buildTree(0, 0, nbCol-1);
	while (nbRequetes--)
	{
		int t, l, r, v;
		cin >> t >> l >> r >> v;
		if (t == 1)
			updateMax(0, l, r, v);
		else
			updateMin(0, l, r, v);
	}
	recursivePush(0);
	for (int i(0); i < nbCol; ++i)
		cout << val[i] << '\n';
}*/

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