oj.uz

답안 #1081976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1081976 2024-08-30T13:41:52 Z DarkMatter 벽 (IOI14_wall) C++17
100 / 100
 712 ms 120488 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
struct SegmentTree
{
	int n;
	vector<int>seg;
	vector<pair<int, int>>lazy;
	SegmentTree(int _n) {
		n = _n;
		seg.resize(4 * n + 5, 0);
		lazy.resize(4 * n + 5, { 1e9 + 7,-1 });
	}
	void push(int x, int lx, int rx) {
		if (lx == rx)
			return;
		if (lazy[x].first != 1e9) {
			seg[2 * x] = min(seg[2 * x], lazy[x].first);
			lazy[2 * x].first = min(lazy[2 * x].first, lazy[x].first);
			lazy[2 * x].second = min(lazy[2 * x].second, lazy[x].first);
			seg[2 * x + 1] = min(seg[2 * x + 1], lazy[x].first);
			lazy[2 * x + 1].first = min(lazy[2 * x + 1].first, lazy[x].first);
			lazy[2 * x + 1].second = min(lazy[2 * x + 1].second, lazy[x].first);
		}
		if (lazy[x].second != -1) {
			seg[2 * x] = max(seg[2 * x], lazy[x].second);
			lazy[2 * x].first = max(lazy[2 * x].first, lazy[x].second);
			lazy[2 * x].second = max(lazy[2 * x].second, lazy[x].second);
			seg[2 * x + 1] = max(seg[2 * x + 1], lazy[x].second);
			lazy[2 * x + 1].first = max(lazy[2 * x + 1].first, lazy[x].second);
			lazy[2 * x + 1].second = max(lazy[2 * x + 1].second, lazy[x].second);
		}
		lazy[x] = { 1e9,-1 };
	}
	void update(int x, int lx, int rx, int l, int r, int type, int v) {
		push(x, lx, rx);
		if (lx > rx || l > rx || lx > r)
			return;
		if (lx >= l && rx <= r) {
			if (type == 1)
				seg[x] = max(seg[x], v), lazy[x].first = max(lazy[x].first, v), lazy[x].second = max(lazy[x].second, v);
			else
				seg[x] = min(seg[x], v), lazy[x].first = min(lazy[x].first, v), lazy[x].second = min(lazy[x].second, v);
			//push(x, lx, rx);
			return;
		}
		int mid = (lx + rx) / 2;
		update(2 * x, lx, mid, l, r, type, v);
		update(2 * x + 1, mid + 1, rx, l, r, type, v);
	}
	int get(int x, int lx, int rx, int i) {
		if (lx == rx)
			return seg[x];
		push(x, lx, rx);
		int mid = (lx + rx) / 2;
		if (i <= mid)
			return get(2 * x, lx, mid, i);
		else
			return get(2 * x + 1, mid + 1, rx, i);
	}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	for (int i = 0; i < n; i++)
		finalHeight[i] = 0;
	SegmentTree seg(n);
	for (int i = 0; i < k; i++)
		seg.update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
	for (int i = 0; i < n; i++)
		finalHeight[i] = seg.get(1, 0, n - 1, i);
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 5 ms 892 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 89 ms 13904 KB Output is correct
3 Correct 137 ms 8272 KB Output is correct
4 Correct 401 ms 22704 KB Output is correct
5 Correct 198 ms 23296 KB Output is correct
6 Correct 195 ms 21840 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 89 ms 13996 KB Output is correct
9 Correct 138 ms 8388 KB Output is correct
10 Correct 389 ms 22868 KB Output is correct
11 Correct 202 ms 23428 KB Output is correct
12 Correct 215 ms 21900 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 114 ms 13980 KB Output is correct
15 Correct 27 ms 2136 KB Output is correct
16 Correct 504 ms 22868 KB Output is correct
17 Correct 206 ms 22352 KB Output is correct
18 Correct 216 ms 22536 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1112 KB Output is correct
5 Correct 4 ms 892 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 88 ms 13844 KB Output is correct
9 Correct 154 ms 8388 KB Output is correct
10 Correct 404 ms 22868 KB Output is correct
11 Correct 204 ms 23380 KB Output is correct
12 Correct 211 ms 21928 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 85 ms 13840 KB Output is correct
15 Correct 26 ms 2136 KB Output is correct
16 Correct 507 ms 22872 KB Output is correct
17 Correct 218 ms 22372 KB Output is correct
18 Correct 221 ms 22356 KB Output is correct
19 Correct 654 ms 120404 KB Output is correct
20 Correct 669 ms 120400 KB Output is correct
21 Correct 712 ms 120404 KB Output is correct
22 Correct 665 ms 120400 KB Output is correct
23 Correct 665 ms 120404 KB Output is correct
24 Correct 664 ms 120488 KB Output is correct
25 Correct 682 ms 120456 KB Output is correct
26 Correct 669 ms 120452 KB Output is correct
27 Correct 688 ms 120400 KB Output is correct
28 Correct 679 ms 120260 KB Output is correct
29 Correct 662 ms 120400 KB Output is correct
30 Correct 656 ms 120244 KB Output is correct