Submission #393835

#	Time	Username	Problem	Language	Result	Execution time	Memory
393835		Mounir	Wall (IOI14_wall)	C++14	100 / 100	1567 ms	69548 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(s) (int)s.size()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;
 
const int N = (1 << 21), OO = INT_MAX;
 
struct Noeud {
	int bornes[2];
};

Noeud arbre[N * 2];

void init(){
	for (int noeud = 1; noeud < 2 * N; ++noeud){
		arbre[noeud].bornes[0] = 0;
		arbre[noeud].bornes[1] = OO;
	}
}

void prop(int noeud){
	for (int enfant = noeud * 2; enfant <= noeud * 2 + 1; ++enfant){
		for (int iBorne = 0; iBorne < 2; ++iBorne){
			chmin(arbre[enfant].bornes[iBorne], arbre[noeud].bornes[1]);
			chmax(arbre[enfant].bornes[iBorne], arbre[noeud].bornes[0]);
		}
	}
}

void add(int noeud, int curl, int curr, int reql, int reqr, int typeReq, int val){
	if (curl > reqr || reql > curr)
		return;
	if (reql <= curl && curr <= reqr){
		for (int iBorne = 0; iBorne < 2; ++iBorne){
			if (typeReq == 2)
				chmin(arbre[noeud].bornes[iBorne], val);
			else
				chmax(arbre[noeud].bornes[iBorne], val);
		//	cout << "REQ " << arbre[noeud].bornes[0] << " " << arbre[noeud].bornes[1] << endl;
		}
		return;
	}

	int mid = (curl + curr)/2;
	prop(noeud);
	arbre[noeud].bornes[0] = 0; arbre[noeud].bornes[1] = OO;
	add(noeud * 2, curl, mid, reql, reqr, typeReq, val);
	add(noeud * 2 + 1, mid + 1, curr, reql, reqr, typeReq, val);
}

void toutPropager(int indice){
	add(1, 0, N - 1, indice, indice, 1, 0);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	init();

	int nVals = n, nReqs = k;
	for (int iReq = 0; iReq < nReqs; ++iReq){
		//left[iReq]++; right[iReq]++;
		add(1, 0, N - 1, left[iReq], right[iReq], op[iReq], height[iReq]);
		/*for (int iVal = 0; iVal < nVals; ++iVal){
			toutPropager(iVal);
			cout << arbre[N + iVal].bornes[0] << " ";
		}
		cout << endl;*/
	}

	for (int iVal = 0; iVal < nVals; ++iVal){
		toutPropager(iVal);
		finalHeight[iVal] = arbre[N + iVal].bornes[0];

		//cout << arbre[N + iVal].bornes[0] << " " << arbre[N + iVal].bornes[1] << endl;
	}
	return;
}

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