oj.uz

답안 #741588

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
741588 2023-05-14T12:19:02 Z vjudge1 벽 (IOI14_wall) C++17
100 / 100
 846 ms 69632 KB 
#include "wall.h"
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
const int OFF = (1 << 21);
const int INF = 0x3f3f3f3f;
 
int mx[2 * OFF ], mi[2 * OFF];
 
void spoji(int j,int i){
	int olmi = mi[i];
	mx[i] = min(mx[i], mx[j]);
	mi[i] = max(mi[i], mi[j]);
	if(mi[i] > mx[i]){
		if(olmi < mi[j])
			mx[i] = mi[i];
		else
			mi[i] = mx[i];
	}
}
void prop(int i){
	if(i < OFF){
		spoji(i, 2 * i);
		spoji(i, 2 * i + 1);
		mx[i] = INF, mi[i] = 0;
	}
}
 
void update(int i,int a,int b,int lo,int hi){
	prop(i);
	if(lo <= a && b <= hi){
		spoji(0, i);
		prop(i);
		return;
	}
	if(a > hi || b < lo) return;
	update(2 * i, a, (a + b) / 2, lo, hi);
	update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi);
 
 
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
 
	for(int i = 0;i < k;i++){
		mi[0] = 0, mx[0] = INF;
		if(op[i] == 2) mx[0] = height[i];
		else           mi[0] = height[i];
		update(1, 0, OFF - 1, left[i], right[i]);
	}
	for(int i = 1;i < OFF;i++) prop(i);
	for(int i = 0;i < n;i++) finalHeight[i] = mi[OFF + i];
	return;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 32972 KB Output is correct
2 Correct 31 ms 33116 KB Output is correct
3 Correct 31 ms 33140 KB Output is correct
4 Correct 35 ms 33320 KB Output is correct
5 Correct 33 ms 33324 KB Output is correct
6 Correct 35 ms 33316 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 33044 KB Output is correct
2 Correct 331 ms 46696 KB Output is correct
3 Correct 220 ms 40244 KB Output is correct
4 Correct 526 ms 51036 KB Output is correct
5 Correct 393 ms 52156 KB Output is correct
6 Correct 367 ms 50512 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 33000 KB Output is correct
2 Correct 31 ms 33176 KB Output is correct
3 Correct 31 ms 33040 KB Output is correct
4 Correct 35 ms 33256 KB Output is correct
5 Correct 40 ms 33348 KB Output is correct
6 Correct 35 ms 33292 KB Output is correct
7 Correct 28 ms 33080 KB Output is correct
8 Correct 354 ms 46712 KB Output is correct
9 Correct 228 ms 40252 KB Output is correct
10 Correct 548 ms 51164 KB Output is correct
11 Correct 389 ms 52148 KB Output is correct
12 Correct 375 ms 50696 KB Output is correct
13 Correct 27 ms 33028 KB Output is correct
14 Correct 336 ms 46664 KB Output is correct
15 Correct 69 ms 34284 KB Output is correct
16 Correct 762 ms 51404 KB Output is correct
17 Correct 402 ms 50728 KB Output is correct
18 Correct 382 ms 50808 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 32972 KB Output is correct
2 Correct 33 ms 33152 KB Output is correct
3 Correct 39 ms 33068 KB Output is correct
4 Correct 35 ms 33356 KB Output is correct
5 Correct 33 ms 33356 KB Output is correct
6 Correct 33 ms 33272 KB Output is correct
7 Correct 28 ms 32972 KB Output is correct
8 Correct 366 ms 46652 KB Output is correct
9 Correct 248 ms 40168 KB Output is correct
10 Correct 540 ms 51144 KB Output is correct
11 Correct 383 ms 52104 KB Output is correct
12 Correct 378 ms 50560 KB Output is correct
13 Correct 28 ms 33008 KB Output is correct
14 Correct 367 ms 46724 KB Output is correct
15 Correct 73 ms 34268 KB Output is correct
16 Correct 785 ms 51396 KB Output is correct
17 Correct 393 ms 50804 KB Output is correct
18 Correct 368 ms 50764 KB Output is correct
19 Correct 813 ms 69496 KB Output is correct
20 Correct 796 ms 67056 KB Output is correct
21 Correct 782 ms 69500 KB Output is correct
22 Correct 760 ms 67020 KB Output is correct
23 Correct 765 ms 67024 KB Output is correct
24 Correct 783 ms 66980 KB Output is correct
25 Correct 793 ms 66904 KB Output is correct
26 Correct 846 ms 69632 KB Output is correct
27 Correct 771 ms 69480 KB Output is correct
28 Correct 767 ms 67048 KB Output is correct
29 Correct 798 ms 67008 KB Output is correct
30 Correct 786 ms 66976 KB Output is correct