oj.uz

답안 #58767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58767 2018-07-19T09:39:36 Z Sherazin 벽 (IOI14_wall) C++14
100 / 100
 1161 ms 232428 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1 << 21;

int lo[N << 1], hi[N << 1];
int *ret, S;

void puttag(int p, int low, int high) {
	lo[p] = min(high, max(low, lo[p]));
	hi[p] = max(low, min(high, hi[p]));
}

void pushlz(int p, int l, int r) {
	if(l == r) ret[l] = min(hi[p], max(lo[p], ret[l]));
	else {
		puttag(p << 1, lo[p], hi[p]);
		puttag(p << 1 | 1, lo[p], hi[p]);
	}
	lo[p] = 0;
	hi[p] = INT_MAX;
}

void build(int p = 1, int l = 0, int r = S - 1) {
	hi[p] = INT_MAX;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
}

void update(int x, int y, int low, int high, int p = 1, int l = 0, int r = S - 1) {
	if(x > r || l > y) return;
	if(x <= l && r <= y) return puttag(p, low, high);
	pushlz(p, l, r);
	int mid = (l + r) >> 1;
	update(x, y, low, high, p << 1, l, mid);
	update(x, y, low, high, p << 1 | 1, mid + 1, r);
}

void proc(int p = 1, int l = 0, int r = S - 1) {
	pushlz(p, l, r);
	if(l == r) return;
	int mid = (l + r) >> 1;
	proc(p << 1, l, mid);
	proc(p << 1 | 1, mid + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	ret = finalHeight;
	S = n;
	build();
	for(int i = 0; i < k; i++) {
		if(op[i] == 1) update(left[i], right[i], height[i], INT_MAX);
		else if(op[i] == 2) update(left[i], right[i], 0, height[i]);
	}
	proc();
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 4 ms 616 KB Output is correct
3 Correct 5 ms 616 KB Output is correct
4 Correct 12 ms 1080 KB Output is correct
5 Correct 10 ms 1204 KB Output is correct
6 Correct 9 ms 1308 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1308 KB Output is correct
2 Correct 253 ms 14532 KB Output is correct
3 Correct 342 ms 14532 KB Output is correct
4 Correct 748 ms 30592 KB Output is correct
5 Correct 460 ms 41396 KB Output is correct
6 Correct 478 ms 50048 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 50048 KB Output is correct
2 Correct 6 ms 50048 KB Output is correct
3 Correct 6 ms 50048 KB Output is correct
4 Correct 10 ms 50048 KB Output is correct
5 Correct 10 ms 50048 KB Output is correct
6 Correct 10 ms 50048 KB Output is correct
7 Correct 3 ms 50048 KB Output is correct
8 Correct 217 ms 53132 KB Output is correct
9 Correct 222 ms 53132 KB Output is correct
10 Correct 747 ms 69128 KB Output is correct
11 Correct 429 ms 79656 KB Output is correct
12 Correct 431 ms 88296 KB Output is correct
13 Correct 3 ms 88296 KB Output is correct
14 Correct 270 ms 90876 KB Output is correct
15 Correct 43 ms 90876 KB Output is correct
16 Correct 627 ms 103984 KB Output is correct
17 Correct 376 ms 112932 KB Output is correct
18 Correct 368 ms 121960 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 121960 KB Output is correct
2 Correct 6 ms 121960 KB Output is correct
3 Correct 2 ms 121960 KB Output is correct
4 Correct 11 ms 121960 KB Output is correct
5 Correct 10 ms 121960 KB Output is correct
6 Correct 10 ms 121960 KB Output is correct
7 Correct 3 ms 121960 KB Output is correct
8 Correct 198 ms 125208 KB Output is correct
9 Correct 292 ms 125208 KB Output is correct
10 Correct 654 ms 140512 KB Output is correct
11 Correct 437 ms 150324 KB Output is correct
12 Correct 460 ms 153872 KB Output is correct
13 Correct 3 ms 153872 KB Output is correct
14 Correct 226 ms 153872 KB Output is correct
15 Correct 41 ms 153872 KB Output is correct
16 Correct 713 ms 153872 KB Output is correct
17 Correct 445 ms 153872 KB Output is correct
18 Correct 406 ms 153872 KB Output is correct
19 Correct 960 ms 205836 KB Output is correct
20 Correct 903 ms 211612 KB Output is correct
21 Correct 1012 ms 222044 KB Output is correct
22 Correct 1077 ms 222044 KB Output is correct
23 Correct 1010 ms 222044 KB Output is correct
24 Correct 1126 ms 222044 KB Output is correct
25 Correct 935 ms 222044 KB Output is correct
26 Correct 952 ms 222044 KB Output is correct
27 Correct 906 ms 227212 KB Output is correct
28 Correct 998 ms 232428 KB Output is correct
29 Correct 1161 ms 232428 KB Output is correct
30 Correct 905 ms 232428 KB Output is correct