oj.uz

Submission #240015

# Submission time Handle Problem Language Result Execution time Memory
240015 2020-06-17T17:28:14 Z GREGOIRELC Wall (IOI14_wall) C++14
61 / 100
 3000 ms 53480 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;
			}
		}*/
		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

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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Correct 12 ms 8832 KB Output is correct
3 Correct 13 ms 8448 KB Output is correct
4 Correct 74 ms 8824 KB Output is correct
5 Correct 70 ms 7672 KB Output is correct
6 Correct 78 ms 7672 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6656 KB Output is correct
2 Correct 377 ms 46400 KB Output is correct
3 Correct 355 ms 23592 KB Output is correct
4 Correct 1195 ms 53072 KB Output is correct
5 Correct 1008 ms 53096 KB Output is correct
6 Correct 973 ms 51120 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Correct 12 ms 8732 KB Output is correct
3 Correct 13 ms 8320 KB Output is correct
4 Correct 70 ms 8824 KB Output is correct
5 Correct 69 ms 7672 KB Output is correct
6 Correct 67 ms 7672 KB Output is correct
7 Correct 9 ms 6656 KB Output is correct
8 Correct 389 ms 51728 KB Output is correct
9 Correct 355 ms 27036 KB Output is correct
10 Correct 1131 ms 53008 KB Output is correct
11 Correct 996 ms 53260 KB Output is correct
12 Correct 964 ms 51272 KB Output is correct
13 Correct 10 ms 6656 KB Output is correct
14 Correct 434 ms 51864 KB Output is correct
15 Correct 142 ms 11468 KB Output is correct
16 Correct 1336 ms 53480 KB Output is correct
17 Correct 935 ms 49016 KB Output is correct
18 Correct 969 ms 50592 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6656 KB Output is correct
2 Correct 13 ms 8832 KB Output is correct
3 Correct 11 ms 8320 KB Output is correct
4 Correct 69 ms 8824 KB Output is correct
5 Correct 78 ms 7672 KB Output is correct
6 Correct 73 ms 7676 KB Output is correct
7 Correct 9 ms 6656 KB Output is correct
8 Correct 413 ms 51852 KB Output is correct
9 Correct 363 ms 27048 KB Output is correct
10 Correct 1177 ms 52820 KB Output is correct
11 Correct 985 ms 53108 KB Output is correct
12 Correct 984 ms 51288 KB Output is correct
13 Correct 9 ms 6656 KB Output is correct
14 Correct 420 ms 51848 KB Output is correct
15 Correct 144 ms 11472 KB Output is correct
16 Correct 1281 ms 53440 KB Output is correct
17 Correct 948 ms 49032 KB Output is correct
18 Correct 933 ms 50700 KB Output is correct
19 Execution timed out 3087 ms 52624 KB Time limit exceeded
20 Halted 0 ms 0 KB -