oj.uz

답안 #138207

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138207 2019-07-29T15:16:36 Z Arturgo 벽 (IOI14_wall) C++14
100 / 100
 939 ms 61560 KB 
#include "wall.h"
#include <iostream>
using namespace std;

const int INFINI = 1000 * 1000 * 1000;

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

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 << 21)) {
		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 << 21)) {
	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 << 21);iSommet++)
		update(iSommet);

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

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 33144 KB Output is correct
2 Correct 57 ms 33400 KB Output is correct
3 Correct 55 ms 33144 KB Output is correct
4 Correct 61 ms 33272 KB Output is correct
5 Correct 59 ms 33272 KB Output is correct
6 Correct 59 ms 33352 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 33144 KB Output is correct
2 Correct 487 ms 41128 KB Output is correct
3 Correct 325 ms 36600 KB Output is correct
4 Correct 767 ms 41540 KB Output is correct
5 Correct 482 ms 42144 KB Output is correct
6 Correct 471 ms 42128 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 33272 KB Output is correct
2 Correct 57 ms 33272 KB Output is correct
3 Correct 55 ms 33144 KB Output is correct
4 Correct 62 ms 33260 KB Output is correct
5 Correct 61 ms 33400 KB Output is correct
6 Correct 59 ms 33372 KB Output is correct
7 Correct 53 ms 33144 KB Output is correct
8 Correct 492 ms 41040 KB Output is correct
9 Correct 316 ms 36600 KB Output is correct
10 Correct 760 ms 41620 KB Output is correct
11 Correct 483 ms 42308 KB Output is correct
12 Correct 474 ms 42232 KB Output is correct
13 Correct 54 ms 33144 KB Output is correct
14 Correct 490 ms 41056 KB Output is correct
15 Correct 97 ms 33912 KB Output is correct
16 Correct 860 ms 41856 KB Output is correct
17 Correct 495 ms 41820 KB Output is correct
18 Correct 485 ms 41908 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 33144 KB Output is correct
2 Correct 59 ms 33272 KB Output is correct
3 Correct 54 ms 33144 KB Output is correct
4 Correct 60 ms 33400 KB Output is correct
5 Correct 61 ms 33244 KB Output is correct
6 Correct 59 ms 33272 KB Output is correct
7 Correct 53 ms 33144 KB Output is correct
8 Correct 498 ms 41104 KB Output is correct
9 Correct 319 ms 36580 KB Output is correct
10 Correct 769 ms 41700 KB Output is correct
11 Correct 482 ms 42140 KB Output is correct
12 Correct 474 ms 42104 KB Output is correct
13 Correct 59 ms 33148 KB Output is correct
14 Correct 495 ms 41084 KB Output is correct
15 Correct 98 ms 33784 KB Output is correct
16 Correct 926 ms 41988 KB Output is correct
17 Correct 482 ms 41976 KB Output is correct
18 Correct 484 ms 41864 KB Output is correct
19 Correct 921 ms 59156 KB Output is correct
20 Correct 905 ms 59220 KB Output is correct
21 Correct 909 ms 61560 KB Output is correct
22 Correct 908 ms 58868 KB Output is correct
23 Correct 907 ms 58916 KB Output is correct
24 Correct 939 ms 59012 KB Output is correct
25 Correct 906 ms 58580 KB Output is correct
26 Correct 929 ms 61376 KB Output is correct
27 Correct 911 ms 61172 KB Output is correct
28 Correct 907 ms 58560 KB Output is correct
29 Correct 920 ms 58380 KB Output is correct
30 Correct 909 ms 58488 KB Output is correct