oj.uz

Submission #240011

# Submission time Handle Problem Language Result Execution time Memory
240011 2020-06-17T17:18:49 Z GREGOIRELC Wall (IOI14_wall) C++14
0 / 100
 3000 ms 51760 KB 
#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;
			}
		}
		/*for(int haut : aTester)
		{
			//cout << haut << endl;
			if(haut > 0 && getMax(RACINE, 0, MID - 1, 0, haut - 1, segTreeRetire) < getMax(RACINE, 0, MID - 1, haut, MID - 1, segTreeAjout))
			{
				curHauteur = max(curHauteur, haut);
			}
			if(haut > 1 && getMax(RACINE, 0, MID - 1, 0, haut-2, segTreeRetire) < getMax(RACINE, 0, MID - 1, haut-1, MID - 1, segTreeAjout))
			{
				curHauteur = max(curHauteur, haut - 1);
			}
			if(getMax(RACINE, 0, MID - 1, 0, haut, segTreeRetire) < getMax(RACINE, 0, MID - 1, haut + 1, MID - 1, segTreeAjout))
			{
				curHauteur = max(curHauteur, haut + 1);
			}
		}*/
		finalHeight[curPos] = curHauteur;
	}
}

Compilation message

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6656 KB Output is correct
2 Correct 40 ms 8832 KB Output is correct
3 Execution timed out 3077 ms 8552 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6656 KB Output is correct
2 Correct 388 ms 51760 KB Output is correct
3 Execution timed out 3070 ms 23996 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6656 KB Output is correct
2 Correct 45 ms 8704 KB Output is correct
3 Execution timed out 3079 ms 8448 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6656 KB Output is correct
2 Correct 45 ms 8724 KB Output is correct
3 Execution timed out 3078 ms 8572 KB Time limit exceeded
4 Halted 0 ms 0 KB -