Submission #240171

#	Time	Username	Problem	Language	Result	Execution time	Memory
240171		GREGOIRELC	Wall (IOI14_wall)	C++14	100 / 100	739 ms	77560 KiB

wall

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include "wall.h"

using namespace std;

const int MAX_POS = 2e6;
const int TAILLE_MAX = 1e5 + 1;
const int MAX_NOEUD = 1 << 22;
const int MID = 1 << 21;
const int RACINE = 1;

pair<int, int> lazy[MAX_NOEUD];
int hauteursFinales[MAX_POS];

void propage(int noeud)
{
	for(int nxtNoeud = noeud * 2; nxtNoeud <= noeud * 2 + 1; nxtNoeud++)
	{
		lazy[nxtNoeud].first = max(lazy[nxtNoeud].first, lazy[noeud].first);
		lazy[nxtNoeud].first = min(lazy[nxtNoeud].first, lazy[noeud].second);
		lazy[nxtNoeud].second = min(lazy[nxtNoeud].second, lazy[noeud].second);
		lazy[nxtNoeud].second = max(lazy[nxtNoeud].second, lazy[noeud].first);
	}
	lazy[noeud].first = 0;
	lazy[noeud].second = MAX_POS;
}

void update(int noeud, int curDeb, int curFin, int deb, int fin, int tp, int val)
{
	if(curDeb > fin || curFin < deb)
	{
		return;
	}
	if(curDeb >= deb && curFin <= fin)
	{
		if(tp == 1)
		{
			lazy[noeud].first = max(lazy[noeud].first, val);
			lazy[noeud].second = max(lazy[noeud].second, val);
		}
		else
		{
			lazy[noeud].second = min(lazy[noeud].second, val);
			lazy[noeud].first = min(lazy[noeud].first, val);
		}
		return;
	}
	if(curDeb == curFin)
	{
		return;
	}
	propage(noeud);
	int mid = (curDeb + curFin) / 2;
	update(noeud * 2, curDeb, mid, deb, fin, tp, val);
	update(noeud * 2 + 1, mid + 1, curFin, deb, fin, tp, val);
}

void get_Hauteurs_Finales(int noeud, int deb, int fin, int n, int maxi)
{
	//cout << noeud << " " << deb << " " << fin << " " << lazy[noeud].first << " " << lazy[noeud].second << endl;
	if(lazy[noeud].first <= lazy[noeud].second)
	{
		maxi = max(maxi, lazy[noeud].first);
	}
	if(deb == fin || deb > n)
	{
		if(deb < n)
		{
			hauteursFinales[deb] = maxi;
		}
		return;
	}
	propage(noeud);
	int mid = (deb + fin) / 2;
	get_Hauteurs_Finales(noeud * 2, deb, mid, n, maxi);
	get_Hauteurs_Finales(noeud * 2 + 1, mid + 1, fin, n, maxi);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int i = 0; i < MAX_NOEUD; i++)
	{
		lazy[i].first = 0;
		lazy[i].second = MAX_POS;
	}
	for(int i = 0; i < k; i++)
	{
		update(1, 0, MID - 1, left[i], right[i], op[i], height[i]);
	}
	get_Hauteurs_Finales(1, 0, MID - 1, n, 0);
	for(int i = 0; i < n; i++)
	{
		finalHeight[i] = hauteursFinales[i];
	}
}

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