oj.uz

답안 #426044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
426044 2021-06-13T13:13:15 Z Mounir 벽 (IOI14_wall) C++14
100 / 100
 1643 ms 94388 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;

const int N = (1 << 22), OO = 1e9;
struct Noeud {
	int valMin, valMax;
};

Noeud arbre[N * 2];
void push(int noeud){
	for (int enfant = noeud * 2; enfant <= noeud * 2 + 1; ++enfant){
		chmin(arbre[enfant].valMin, arbre[noeud].valMax);
		chmin(arbre[enfant].valMax, arbre[noeud].valMax);

		chmax(arbre[enfant].valMin, arbre[noeud].valMin);
		chmax(arbre[enfant].valMax, arbre[noeud].valMin);
	}

	arbre[noeud] = {0, OO};
}

void update(int noeud, int curl, int curr, int reql, int reqr, int typeOp, int val){
	if (curl > reqr || reql > curr)
		return;
	if (reql <= curl && curr <= reqr){
		if (typeOp == 2){
			chmin(arbre[noeud].valMin, val);
			chmin(arbre[noeud].valMax, val);
		}
		else {
			chmax(arbre[noeud].valMin, val);
			chmax(arbre[noeud].valMax, val);
		}
		return;
	}

	push(noeud);
	int mid = (curl + curr)/2;
	update(noeud * 2, curl, mid, reql, reqr, typeOp, val);
	update(noeud * 2 + 1, mid + 1, curr, reql, reqr, typeOp, val);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int noeud = 1; noeud < 2 * N; ++noeud)
		arbre[noeud] = {0, OO};

	for (int iReq = 0; iReq < k; ++iReq)
		update(1, 0, N - 1, left[iReq], right[iReq], op[iReq], height[iReq]);
	
	for (int ind = 0; ind < n; ++ind){
		update(1, 0, N - 1, ind, ind, 2, OO);
		finalHeight[ind] = arbre[N + ind].valMin;
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 65860 KB Output is correct
2 Correct 40 ms 65968 KB Output is correct
3 Correct 38 ms 65976 KB Output is correct
4 Correct 52 ms 66180 KB Output is correct
5 Correct 56 ms 66196 KB Output is correct
6 Correct 45 ms 66132 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 65860 KB Output is correct
2 Correct 392 ms 74772 KB Output is correct
3 Correct 282 ms 70256 KB Output is correct
4 Correct 627 ms 76244 KB Output is correct
5 Correct 486 ms 76776 KB Output is correct
6 Correct 469 ms 76704 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 65836 KB Output is correct
2 Correct 41 ms 65988 KB Output is correct
3 Correct 49 ms 65980 KB Output is correct
4 Correct 48 ms 66132 KB Output is correct
5 Correct 55 ms 66116 KB Output is correct
6 Correct 47 ms 66144 KB Output is correct
7 Correct 43 ms 65840 KB Output is correct
8 Correct 416 ms 75264 KB Output is correct
9 Correct 260 ms 70736 KB Output is correct
10 Correct 601 ms 76744 KB Output is correct
11 Correct 459 ms 77380 KB Output is correct
12 Correct 447 ms 77252 KB Output is correct
13 Correct 44 ms 65860 KB Output is correct
14 Correct 384 ms 75324 KB Output is correct
15 Correct 83 ms 67140 KB Output is correct
16 Correct 643 ms 77092 KB Output is correct
17 Correct 434 ms 77004 KB Output is correct
18 Correct 458 ms 77124 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 65880 KB Output is correct
2 Correct 49 ms 65956 KB Output is correct
3 Correct 45 ms 65948 KB Output is correct
4 Correct 54 ms 66132 KB Output is correct
5 Correct 51 ms 66116 KB Output is correct
6 Correct 49 ms 66072 KB Output is correct
7 Correct 40 ms 65908 KB Output is correct
8 Correct 389 ms 75168 KB Output is correct
9 Correct 265 ms 70724 KB Output is correct
10 Correct 606 ms 76748 KB Output is correct
11 Correct 439 ms 77296 KB Output is correct
12 Correct 446 ms 77356 KB Output is correct
13 Correct 41 ms 65884 KB Output is correct
14 Correct 387 ms 75248 KB Output is correct
15 Correct 76 ms 67140 KB Output is correct
16 Correct 600 ms 77076 KB Output is correct
17 Correct 450 ms 77008 KB Output is correct
18 Correct 466 ms 77064 KB Output is correct
19 Correct 1476 ms 94388 KB Output is correct
20 Correct 1537 ms 90884 KB Output is correct
21 Correct 1590 ms 93428 KB Output is correct
22 Correct 1632 ms 90940 KB Output is correct
23 Correct 1530 ms 90960 KB Output is correct
24 Correct 1476 ms 90912 KB Output is correct
25 Correct 1539 ms 90912 KB Output is correct
26 Correct 1534 ms 93460 KB Output is correct
27 Correct 1518 ms 93504 KB Output is correct
28 Correct 1583 ms 90980 KB Output is correct
29 Correct 1643 ms 90928 KB Output is correct
30 Correct 1546 ms 91012 KB Output is correct