oj.uz

답안 #779755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779755 2023-07-11T18:40:55 Z zsombor 벽 (IOI14_wall) C++17
8 / 100
 3000 ms 114816 KB 
#include <iostream>
#include <vector>
#include "wall.h"
using namespace std;

struct node {
	int L, M, R, MN, MX;
	node() { MN = 0; MX = 1e5; }
};

vector <node> sgt(5e6, node());
vector <int> ans(2e6);

void build_sgt(int x, int l, int r) {
	sgt[x].L = l;
	sgt[x].M = (l + r) / 2;
	sgt[x].R = r;
	if (r - l == 1) { sgt[x].MX = 0; return; }
	build_sgt(2 * x, l, (l + r) / 2);
	build_sgt(2 * x + 1, (l + r) / 2, r);
}

void update_node(int x, int mn, int mx) {
	if (mx < sgt[x].MN) { sgt[x].MN = sgt[x].MX = mx; return; }
	if (mn > sgt[x].MX) { sgt[x].MN = sgt[x].MX = mn; return; }
	sgt[x].MN = max(sgt[x].MN, mn);
	sgt[x].MX = min(sgt[x].MX, mx);
}

void push_down(int x) {
	if (sgt[x].R - sgt[x].L == 1) return;
	update_node(2 * x, sgt[x].MN, sgt[x].MX);
	update_node(2 * x + 1, sgt[x].MN, sgt[x].MX);
	sgt[x].L = 0;
	sgt[x].R = 1e5;
}

void update(int x, int l, int r, int mn, int mx) {
	push_down(x);
	if (r <= sgt[x].L || sgt[x].R <= l) return;
	if (l <= sgt[x].L && sgt[x].R <= r) { update_node(x, mn, mx); return; }
	update(2 * x, l, r, mn, mx);
	update(2 * x + 1, l, r, mn, mx);
}

void get_ans(int x) {
	if (sgt[x].R - sgt[x].L == 1) { ans[sgt[x].L] = sgt[x].MN; return; }
	push_down(x);
	get_ans(2 * x);
	get_ans(2 * x + 1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	build_sgt(1, 0, n);
	for (int i = 0; i < k; i++) {
		if (op[i] == 1) update(1, left[i], right[i] + 1, height[i], 1e5);
		else update(1, left[i], right[i] + 1, 0, height[i]);
	}
	get_ans(1);
	for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 105932 KB Output is correct
2 Correct 39 ms 106068 KB Output is correct
3 Correct 46 ms 105952 KB Output is correct
4 Correct 737 ms 106176 KB Output is correct
5 Correct 737 ms 106172 KB Output is correct
6 Correct 751 ms 106176 KB Output is correct

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 105976 KB Output is correct
2 Correct 139 ms 114068 KB Output is correct
3 Execution timed out 3064 ms 109552 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 105928 KB Output is correct
2 Correct 40 ms 106036 KB Output is correct
3 Correct 49 ms 105968 KB Output is correct
4 Correct 746 ms 106172 KB Output is correct
5 Correct 745 ms 106172 KB Output is correct
6 Correct 738 ms 106180 KB Output is correct
7 Correct 40 ms 105904 KB Output is correct
8 Correct 147 ms 114788 KB Output is correct
9 Execution timed out 3066 ms 110212 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 105932 KB Output is correct
2 Correct 41 ms 106060 KB Output is correct
3 Correct 48 ms 105924 KB Output is correct
4 Correct 738 ms 106172 KB Output is correct
5 Correct 767 ms 106272 KB Output is correct
6 Correct 749 ms 106284 KB Output is correct
7 Correct 44 ms 105932 KB Output is correct
8 Correct 159 ms 114816 KB Output is correct
9 Execution timed out 3065 ms 110196 KB Time limit exceeded
10 Halted 0 ms 0 KB -