Submission #426044

#	Time	Username	Problem	Language	Result	Execution time	Memory
426044		Mounir	Wall (IOI14_wall)	C++14	100 / 100	1643 ms	94388 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;

const int N = (1 << 22), OO = 1e9;
struct Noeud {
	int valMin, valMax;
};

Noeud arbre[N * 2];
void push(int noeud){
	for (int enfant = noeud * 2; enfant <= noeud * 2 + 1; ++enfant){
		chmin(arbre[enfant].valMin, arbre[noeud].valMax);
		chmin(arbre[enfant].valMax, arbre[noeud].valMax);

		chmax(arbre[enfant].valMin, arbre[noeud].valMin);
		chmax(arbre[enfant].valMax, arbre[noeud].valMin);
	}

	arbre[noeud] = {0, OO};
}

void update(int noeud, int curl, int curr, int reql, int reqr, int typeOp, int val){
	if (curl > reqr || reql > curr)
		return;
	if (reql <= curl && curr <= reqr){
		if (typeOp == 2){
			chmin(arbre[noeud].valMin, val);
			chmin(arbre[noeud].valMax, val);
		}
		else {
			chmax(arbre[noeud].valMin, val);
			chmax(arbre[noeud].valMax, val);
		}
		return;
	}

	push(noeud);
	int mid = (curl + curr)/2;
	update(noeud * 2, curl, mid, reql, reqr, typeOp, val);
	update(noeud * 2 + 1, mid + 1, curr, reql, reqr, typeOp, val);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int noeud = 1; noeud < 2 * N; ++noeud)
		arbre[noeud] = {0, OO};

	for (int iReq = 0; iReq < k; ++iReq)
		update(1, 0, N - 1, left[iReq], right[iReq], op[iReq], height[iReq]);
	
	for (int ind = 0; ind < n; ++ind){
		update(1, 0, N - 1, ind, ind, 2, OO);
		finalHeight[ind] = arbre[N + ind].valMin;
	}
}

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