Submission #387514

#	Time	Username	Problem	Language	Result	Execution time	Memory
387514		peijar	Wall (IOI14_wall)	C++17	61 / 100	850 ms	145088 KiB

wall

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

const int MAXN = 4e6+10;
const int INF = 1e9;

int segVal[MAXN], lazyMax[MAXN], lazyMin[MAXN];
int iDeb[MAXN], iFin[MAXN];

void buildTree(int iNoeud, int li, int ri)
{
	iDeb[iNoeud] = li, iFin[iNoeud] = ri;
	lazyMax[iNoeud] = 0;
	lazyMin[iNoeud] = INF;
	if (li == ri)
		return;

	buildTree(2*iNoeud, li, (li+ri)/2);
	buildTree(2*iNoeud+1, (li+ri)/2+1, ri);
}

void changeMax(int iNoeud, int val)
{
	lazyMax[iNoeud] = max(lazyMax[iNoeud], val);
	lazyMin[iNoeud] = max(lazyMin[iNoeud], val);
}

void changeMin(int iNoeud, int val)
{
	lazyMin[iNoeud] = min(lazyMin[iNoeud], val);
	lazyMax[iNoeud] = min(lazyMax[iNoeud], val);
}

void pushDown(int iNoeud)
{
	segVal[iNoeud] = max(segVal[iNoeud], lazyMax[iNoeud]);
	segVal[iNoeud] = min(segVal[iNoeud], lazyMin[iNoeud]);
	if (iDeb[iNoeud] < iFin[iNoeud])
	{
		changeMax(2*iNoeud, lazyMax[iNoeud]);
		changeMin(2*iNoeud, lazyMin[iNoeud]);
		changeMax(2*iNoeud+1, lazyMax[iNoeud]);
		changeMin(2*iNoeud+1, lazyMin[iNoeud]);
	}
	lazyMax[iNoeud] = 0, lazyMin[iNoeud] = INF;
}

int getVal(int iNoeud, int pos)
{
	pushDown(iNoeud);
	if (iDeb[iNoeud] > pos or iFin[iNoeud] < pos) return 0;
	if (iDeb[iNoeud] == iFin[iNoeud])
		return segVal[iNoeud];
	return getVal(2*iNoeud, pos) + getVal(2*iNoeud+1, pos);
}

void update(int iNoeud, int deb, int fin, int op, int val)
{
	pushDown(iNoeud);
	if (deb > iFin[iNoeud] or fin < iDeb[iNoeud])
		return;
	if (deb <= iDeb[iNoeud] and iFin[iNoeud] <= fin)
	{
		if (op==1)
			lazyMax[iNoeud] = val;
		else
			lazyMin[iNoeud] = val;
		pushDown(iNoeud);
		return ;
	}
	update(2*iNoeud, deb, fin, op, val);
	update(2*iNoeud+1, deb, fin, op, val);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	buildTree(1, 0, n-1);
	for (int i(0); i < k; ++i)
		update(1, left[i], right[i], op[i], height[i]);
	for (int i(0); i < n; ++i)
		finalHeight[i] = getVal(1, i);
  return;
}

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