답안 #49574

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49574 2018-05-31T11:03:25 Z khsoo01 벽 (IOI14_wall) C++11
100 / 100
1309 ms 162944 KB
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int L = (1<<21), inf = 1e9;

struct SEG {
	int mn[2*L], mx[2*L];
	void init () {
		for(int i=2*L;i--;) {
			mn[i] = 0;
			mx[i] = inf;
		}
	}
	void relax (int P, int O, int V) {
		if(O == 1) {
			mn[P] = max(mn[P], V);
			if(mn[P] > mx[P]) mx[P] = mn[P];
		}
		else {
			mx[P] = min(mx[P], V);
			if(mn[P] > mx[P]) mn[P] = mx[P];
		}
	}
	void lazydown (int P) {
		relax(2*P, 1, mn[P]);
		relax(2*P, 2, mx[P]);
		relax(2*P+1, 1, mn[P]);
		relax(2*P+1, 2, mx[P]);
		mn[P] = 0;
		mx[P] = inf;
	}
	void upd (int S, int E, int O, int V, int SS = 0, int SE = L-1, int P = 1) {
		if(S <= SS && SE <= E) {
			relax(P, O, V);
			return;
		}
		if(E < SS || SE < S) return;
		lazydown(P);
		int M = (SS+SE)/2;
		upd(S, E, O, V, SS, M, 2*P);
		upd(S, E, O, V, M+1, SE, 2*P+1);
	}
	int get (int I, int SS = 0, int SE = L-1, int P = 1) {
		if(SS == SE) return mn[P];
		lazydown(P);
		int M = (SS+SE)/2;
		return I <= M ? get(I, SS, M, 2*P) : get(I, M+1, SE, 2*P+1);
	}
} seg;

void buildWall (int N, int K, int O[], int L[], int R[], int H[], int FH[]){
	seg.init();
	for(int i=0;i<K;i++) {
		seg.upd(L[i], R[i], O[i], H[i]);
	}
	for(int i=0;i<N;i++) {
		FH[i] = seg.get(i);
	}
}

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 33144 KB Output is correct
2 Correct 32 ms 33472 KB Output is correct
3 Correct 28 ms 33472 KB Output is correct
4 Correct 35 ms 33568 KB Output is correct
5 Correct 34 ms 33840 KB Output is correct
6 Correct 33 ms 34072 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 34072 KB Output is correct
2 Correct 455 ms 47456 KB Output is correct
3 Correct 248 ms 47456 KB Output is correct
4 Correct 654 ms 61508 KB Output is correct
5 Correct 551 ms 72284 KB Output is correct
6 Correct 397 ms 80692 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 80692 KB Output is correct
2 Correct 35 ms 80692 KB Output is correct
3 Correct 34 ms 80692 KB Output is correct
4 Correct 38 ms 80692 KB Output is correct
5 Correct 41 ms 80692 KB Output is correct
6 Correct 37 ms 80692 KB Output is correct
7 Correct 28 ms 80692 KB Output is correct
8 Correct 521 ms 85820 KB Output is correct
9 Correct 277 ms 85820 KB Output is correct
10 Correct 689 ms 99856 KB Output is correct
11 Correct 411 ms 110348 KB Output is correct
12 Correct 397 ms 118996 KB Output is correct
13 Correct 28 ms 118996 KB Output is correct
14 Correct 455 ms 124000 KB Output is correct
15 Correct 79 ms 124000 KB Output is correct
16 Correct 891 ms 134856 KB Output is correct
17 Correct 386 ms 143752 KB Output is correct
18 Correct 363 ms 145692 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 145692 KB Output is correct
2 Correct 44 ms 145692 KB Output is correct
3 Correct 27 ms 145692 KB Output is correct
4 Correct 40 ms 145692 KB Output is correct
5 Correct 36 ms 145692 KB Output is correct
6 Correct 34 ms 145692 KB Output is correct
7 Correct 25 ms 145692 KB Output is correct
8 Correct 454 ms 145692 KB Output is correct
9 Correct 240 ms 145692 KB Output is correct
10 Correct 715 ms 145692 KB Output is correct
11 Correct 390 ms 146020 KB Output is correct
12 Correct 367 ms 146020 KB Output is correct
13 Correct 28 ms 146020 KB Output is correct
14 Correct 563 ms 146020 KB Output is correct
15 Correct 72 ms 146020 KB Output is correct
16 Correct 1185 ms 146020 KB Output is correct
17 Correct 396 ms 146020 KB Output is correct
18 Correct 392 ms 146020 KB Output is correct
19 Correct 1089 ms 162944 KB Output is correct
20 Correct 1016 ms 162944 KB Output is correct
21 Correct 1016 ms 162944 KB Output is correct
22 Correct 1102 ms 162944 KB Output is correct
23 Correct 1209 ms 162944 KB Output is correct
24 Correct 1309 ms 162944 KB Output is correct
25 Correct 1002 ms 162944 KB Output is correct
26 Correct 1002 ms 162944 KB Output is correct
27 Correct 1197 ms 162944 KB Output is correct
28 Correct 1079 ms 162944 KB Output is correct
29 Correct 998 ms 162944 KB Output is correct
30 Correct 1072 ms 162944 KB Output is correct