Submission #108110

#	Time	Username	Problem	Language	Result	Execution time	Memory
108110		hugo_pm	Wall (IOI14_wall)	C++17	100 / 100	1306 ms	92208 KiB

wall

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

#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const int BIG = (int)(1e9);

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int borne = 2*1000*1000 + 5;
int down[4*borne];
int up[4*borne];
int rep[borne];

void takeDown(int nod, int liv, int riv, int lop, int rop, int val);
void takeUp(int nod, int liv, int riv, int lop, int rop, int val);

void push(int nod, int liv, int riv)
{
	int mm =(liv+riv) / 2;
	takeDown(2*nod, liv, mm, liv, mm, down[nod]);
	takeUp(2*nod, liv, mm, liv, mm, up[nod]);

	takeDown(2*nod+1, mm+1, riv, mm+1, riv, down[nod]);
	takeUp(2*nod+1, mm+1, riv, mm+1, riv, up[nod]);

	down[nod] = BIG;
	up[nod] = 0;
}

void takeDown(int nod, int liv, int riv, int lop, int rop, int val)
{
	if (lop <= liv && riv <= rop) {
		chmin(down[nod], val);
		chmin(up[nod], down[nod]);
		return;
	}
	if (lop > riv || rop < liv) return;
	push(nod,liv,riv);
	int mm = (liv+riv) / 2;
	takeDown(2*nod, liv, mm, lop, rop, val);
	takeDown(2*nod + 1, mm+1, riv, lop, rop, val);
}

void takeUp(int nod, int liv, int riv, int lop, int rop, int val)
{
	if (lop <= liv && riv <= rop) {
		chmax(up[nod], val);
		chmax(down[nod], up[nod]);
		return;
	}
	if (lop > riv || rop < liv) return;
	push(nod,liv,riv);
	int mm = (liv+riv) / 2;
	takeUp(2*nod, liv, mm, lop, rop, val);
	takeUp(2*nod + 1, mm+1, riv, lop, rop, val);
}

void con(int nod, int liv, int riv)
{
	if (liv == riv) {
		rep[liv] = min(down[nod], up[nod]);
		return;
	}
	push(nod,liv,riv);
	int mm = (liv+riv) / 2;
	con(2*nod, liv, mm);
	con(2*nod+1, mm+1, riv);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	form(i, 4*borne) down[i] = BIG;
	form(i, k) {
		if (op[i] == 1) takeUp(1, 0, n-1, left[i], right[i], height[i]);
		else takeDown(1, 0, n-1, left[i], right[i], height[i]);
	}
	con(1, 0, n-1);
	form(i, n) finalHeight[i] = rep[i];
}

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