Submission #240015

#	Time	Username	Problem	Language	Result	Execution time	Memory
240015		GREGOIRELC	Wall (IOI14_wall)	C++14	61 / 100	3087 ms	53480 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 << 18;
const int MID = 1 << 17;
const int RACINE = 1;

struct Info
{
	int deb, fin, haut, tp, tps;
	bool operator<(const Info &other)
	{
		return deb < other.deb;
	}
};

int segTreeAjout[MAX_NOEUD], segTreeRetire[MAX_NOEUD];
vector<Info> debutModif, finModif;
priority_queue<pair<int, int> > vuAjout[TAILLE_MAX], vuRetire[TAILLE_MAX];

void update(int pos, int segTree[], int val)
{
	pos += MID;
	segTree[pos] = val;
	pos /= 2;
	while(pos > 0)
	{
		segTree[pos] = max(segTree[pos * 2], segTree[pos * 2 + 1]);
		pos /= 2;
	}
}

int getMax(int noeud, int curDeb, int curFin, int deb, int fin, int segTree[])
{
	//cout << noeud << endl;
	if(deb > curFin || fin < curDeb)
	{
		return 0;
	}
	if(curDeb >= deb && curFin <= fin)
	{
		return segTree[noeud];
	}
	if(curDeb == curFin)
	{
		return 0;
	}
	int mid = (curDeb + curFin) / 2;
	return max(getMax(noeud * 2, curDeb, mid, deb, fin, segTree), getMax(noeud * 2 + 1, mid + 1, curFin, deb, fin, segTree));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int iModif = 0; iModif < k; iModif++)
	{
		debutModif.push_back({left[iModif], right[iModif], height[iModif], op[iModif], iModif + 1});
		finModif.push_back({right[iModif], right[iModif], height[iModif], op[iModif], iModif + 1});
	}
	sort(debutModif.begin(), debutModif.end());
	sort(finModif.begin(), finModif.end());
	int curDeb = 0, curFin = 0, curHauteur = 0;
	for(int curPos = 0; curPos < n; curPos++)
	{
		vector<int> aTester;
		aTester.push_back(curHauteur);
		//cout << 1 << endl;
		for(; (curDeb < k) && (debutModif[curDeb].deb) <= curPos; curDeb++)
		{
			int deb = debutModif[curDeb].deb, fin = debutModif[curDeb].fin;
			int haut = debutModif[curDeb].haut, tp = debutModif[curDeb].tp, tps = debutModif[curDeb].tps;
			aTester.push_back(haut);
			//cout << deb << " " << fin << " " << haut << " " << tp << " " << tps << endl;
			//cout << 11 << " " << deb << endl;
			if(tp == 1)
			{
				vuAjout[haut].push({tps, fin});
				while(vuAjout[haut].top().second < curPos)
				{
					vuAjout[haut].pop();
				}
				update(haut, segTreeAjout, vuAjout[haut].top().first);
			}
			else
			{
				vuRetire[haut].push({tps, fin});
				while(vuRetire[haut].top().second < curPos)
				{
					vuRetire[haut].pop();
				}
				update(haut, segTreeRetire, vuRetire[haut].top().first);
			}
		}
		//cout << 2 << endl;
		for(; (curFin < k) && (finModif[curFin].deb < curPos); curFin++)
		{
			int fin = finModif[curFin].deb;
			int haut = finModif[curFin].haut, tp = finModif[curFin].tp, tps = finModif[curFin].tps;
			aTester.push_back(haut);
			//cout << fin << " " << haut << " " << tp << " " << tps << endl;
			if(tp == 1)
			{
				while(!vuAjout[haut].empty() && vuAjout[haut].top().second < curPos)
				{
					vuAjout[haut].pop();
				}
				int val = 0;
				if(!vuAjout[haut].empty())
				{
					val = vuAjout[haut].top().first;
				}
				update(haut, segTreeAjout, val);
			}
			else
			{
				while(!vuRetire[haut].empty() && vuRetire[haut].top().second < curPos)
				{
					vuRetire[haut].pop();
				}
				int val = 0;
				if(!vuRetire[haut].empty())
				{
					val = vuRetire[haut].top().first;
				}
				update(haut, segTreeRetire, val);
			}
		}
		curHauteur = 0;
		/*for(int haut = 1; haut <= TAILLE_MAX; haut++)
		{
			//cout << curPos << " " << haut << " " << getMax(RACINE, 0, MID - 1, 0, haut - 1, segTreeRetire) << " " << getMax(RACINE, 0, MID - 1, haut, MID - 1, segTreeAjout) << endl; 
			if(getMax(RACINE, 0, MID - 1, 0, haut - 1, segTreeRetire) < getMax(RACINE, 0, MID - 1, haut, MID - 1, segTreeAjout))
			{
				curHauteur = haut;
			}
		}*/
		int deb = 0, fin = TAILLE_MAX;
		while(deb < fin - 1)
		{
			int mid = (deb + fin) / 2;
			if(getMax(RACINE, 0, MID - 1, 0, mid - 1, segTreeRetire) < getMax(RACINE, 0, MID - 1, mid, MID - 1, segTreeAjout))
			{
				deb = mid;
			}
			else
			{
				fin = mid;
			}
		}
		if(getMax(RACINE, 0, MID - 1, 0, fin - 1, segTreeRetire) < getMax(RACINE, 0, MID - 1, fin, MID - 1, segTreeAjout))
		{
			finalHeight[curPos] = fin;
		}
		else
		{
			finalHeight[curPos] = deb;
		}
	}
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:76:8: warning: unused variable 'deb' [-Wunused-variable]
    int deb = debutModif[curDeb].deb, fin = debutModif[curDeb].fin;
        ^~~
wall.cpp:103:8: warning: unused variable 'fin' [-Wunused-variable]
    int fin = finModif[curFin].deb;
        ^~~
wall.cpp:104:64: warning: unused variable 'tps' [-Wunused-variable]
    int haut = finModif[curFin].haut, tp = finModif[curFin].tp, tps = finModif[curFin].tps;
                                                                ^~~

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