oj.uz

Submission #138206

# Submission time Handle Problem Language Result Execution time Memory
138206 2019-07-29T15:15:15 Z Arturgo Wall (IOI14_wall) C++14
61 / 100
 856 ms 60408 KB 
#include "wall.h"
#include <iostream>
using namespace std;

const int INFINI = 1000 * 1000 * 1000;

pair<int, int> bornes[(1 << 21)];

void push(pair<int, int>& init, pair<int, int> modif) {
	init.first = max(init.first, modif.first);
	init.second = max(init.second, init.first);

	init.second = min(init.second, modif.second);
	init.first = min(init.second, init.first);
}

void update(int noeud) {
	if(noeud >= (1 << 20)) {
		return;
	}

	push(bornes[2 * noeud], bornes[noeud]);
	push(bornes[2 * noeud + 1], bornes[noeud]);
	bornes[noeud] = {0, INFINI};
}

void update(int deb, int fin, pair<int, int> borne, int n = 1, int d = 0, int f = (1 << 20)) {
	update(n);

	if(deb >= f || d >= fin)
		return;
	if(deb <= d && f <= fin) {
		push(bornes[n], borne);
		update(n);
		return;
	}

	int m = (d + f) / 2;
	update(deb, fin, borne, 2 * n, d, m);
	update(deb, fin, borne, 2 * n + 1, m, f);
}

void buildWall(int nbSlots, int nbReqs, int op[], int left[], int right[], int height[], int finalHeight[]) {
	for(int iReq = 0;iReq < nbReqs;iReq++) {
		if(op[iReq] == 1) {
			update(left[iReq], right[iReq] + 1, {height[iReq], INFINI});
		}
		else {
			update(left[iReq], right[iReq] + 1, {0, height[iReq]});
		}
	}

	for(int iSommet = 1;iSommet < (1 << 20);iSommet++)
		update(iSommet);

	for(int iSommet = (1 << 20);iSommet < (1 << 20) + nbSlots;iSommet++) {
		finalHeight[iSommet - (1 << 20)] = bornes[iSommet].first;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16764 KB Output is correct
2 Correct 32 ms 16888 KB Output is correct
3 Correct 30 ms 16760 KB Output is correct
4 Correct 35 ms 16960 KB Output is correct
5 Correct 34 ms 17016 KB Output is correct
6 Correct 33 ms 17016 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16760 KB Output is correct
2 Correct 439 ms 27120 KB Output is correct
3 Correct 287 ms 22876 KB Output is correct
4 Correct 735 ms 27988 KB Output is correct
5 Correct 450 ms 28436 KB Output is correct
6 Correct 440 ms 28536 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16656 KB Output is correct
2 Correct 32 ms 16888 KB Output is correct
3 Correct 29 ms 16760 KB Output is correct
4 Correct 36 ms 17020 KB Output is correct
5 Correct 34 ms 17016 KB Output is correct
6 Correct 34 ms 17016 KB Output is correct
7 Correct 28 ms 16760 KB Output is correct
8 Correct 441 ms 27468 KB Output is correct
9 Correct 304 ms 22904 KB Output is correct
10 Correct 775 ms 28036 KB Output is correct
11 Correct 455 ms 28564 KB Output is correct
12 Correct 436 ms 28428 KB Output is correct
13 Correct 36 ms 16760 KB Output is correct
14 Correct 467 ms 27512 KB Output is correct
15 Correct 72 ms 17912 KB Output is correct
16 Correct 856 ms 28200 KB Output is correct
17 Correct 446 ms 28316 KB Output is correct
18 Correct 449 ms 28168 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16760 KB Output is correct
2 Correct 34 ms 16832 KB Output is correct
3 Correct 29 ms 16760 KB Output is correct
4 Correct 35 ms 17016 KB Output is correct
5 Correct 37 ms 16960 KB Output is correct
6 Correct 38 ms 17016 KB Output is correct
7 Correct 30 ms 16676 KB Output is correct
8 Correct 459 ms 27484 KB Output is correct
9 Correct 292 ms 22896 KB Output is correct
10 Correct 734 ms 28028 KB Output is correct
11 Correct 449 ms 28536 KB Output is correct
12 Correct 443 ms 28536 KB Output is correct
13 Correct 27 ms 16760 KB Output is correct
14 Correct 445 ms 27356 KB Output is correct
15 Correct 70 ms 17912 KB Output is correct
16 Correct 824 ms 28176 KB Output is correct
17 Correct 445 ms 28280 KB Output is correct
18 Correct 446 ms 28052 KB Output is correct
19 Runtime error 503 ms 60408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -