oj.uz

답안 #1009946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009946 2024-06-28T08:12:38 Z stdfloat 벽 (IOI14_wall) C++17
61 / 100
 1413 ms 262144 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

#define ff  first
#define ss  second
#define pii pair<int, int>

vector<int> st;

vector<vector<pii>> lz;

void Lz(int nd, pii p) {
	for (int i = (int)lz[nd].size() - 1; i >= 0; i--)
		if ((lz[nd][i].ff == 1 && p.ff == 1 && lz[nd][i].ss <= p.ss) || (lz[nd][i].ff == 2 && p.ff == 2 && lz[nd][i].ss >= p.ss)) lz[nd].erase(lz[nd].begin() + i);

	for (auto i : lz[nd]) {
		if (i.ff == p.ff) return;
	}

	lz[nd].push_back(p);

	if ((int)lz[nd].size() == 2) {
		if (lz[nd][0].ff == 1) lz[nd][0].ss = min(lz[nd][0].ss, lz[nd][1].ss);
		else lz[nd][0].ss = max(lz[nd][0].ss, lz[nd][1].ss);
	}
}

void LZ(int nd, int l, int r) {
	for (auto [op, h] : lz[nd]) {
		if (op == 1) st[nd] = max(st[nd], h);
		else st[nd] = min(st[nd], h);
	}

	if (l < r) {
		int ch = (nd << 1) + 1;
		for (auto i : lz[nd]) {
			Lz(ch, i); Lz(ch + 1, i);
		}
	}

	lz[nd].clear();
}

int upd(int nd, int l, int r, int x, int y, int op, int h) {
	LZ(nd, l, r);

	if (r < x || y < l) return st[nd];

	if (x <= l && r <= y) {
		Lz(nd, {op, h}); LZ(nd, l, r);
		return st[nd];
	}

	int ch = (nd << 1) + 1, md = (l + r) >> 1;
	return st[nd] = max(upd((nd << 1) + 1, l, md, x, y, op, h), upd(ch + 1, md + 1, r, x, y, op, h));
}

int fnd(int nd, int l, int r, int x) {
	LZ(nd, l, r);

	if (r < x || x < l) return 0;

	if (l == r) return st[nd];

	int ch = (nd << 1) + 1, md = (l + r) >> 1;
	return max(fnd(ch, l, md, x), fnd(ch + 1, md + 1, r, x));
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]) {
	st.assign(n << 2, 0);
	lz.assign(n << 2, {});
	for (int i = 0; i < k; i++) upd(0, 0, n - 1, l[i], r[i], op[i], h[i]);

	for (int i = 0; i < n; i++) fh[i] = fnd(0, 0, n - 1, i);
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 14 ms 2272 KB Output is correct
5 Correct 9 ms 2140 KB Output is correct
6 Correct 7 ms 2308 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 73 ms 8024 KB Output is correct
3 Correct 269 ms 6876 KB Output is correct
4 Correct 937 ms 26192 KB Output is correct
5 Correct 278 ms 26452 KB Output is correct
6 Correct 260 ms 26440 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 14 ms 2188 KB Output is correct
5 Correct 7 ms 2140 KB Output is correct
6 Correct 8 ms 2180 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 82 ms 8020 KB Output is correct
9 Correct 291 ms 6780 KB Output is correct
10 Correct 842 ms 26192 KB Output is correct
11 Correct 296 ms 26452 KB Output is correct
12 Correct 262 ms 26452 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 84 ms 8112 KB Output is correct
15 Correct 74 ms 3924 KB Output is correct
16 Correct 1413 ms 26252 KB Output is correct
17 Correct 303 ms 26260 KB Output is correct
18 Correct 283 ms 26120 KB Output is correct

Subtask #4
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 2 ms 348 KB Output is correct
4 Correct 14 ms 2244 KB Output is correct
5 Correct 7 ms 2260 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 82 ms 8208 KB Output is correct
9 Correct 292 ms 6744 KB Output is correct
10 Correct 962 ms 25944 KB Output is correct
11 Correct 272 ms 26380 KB Output is correct
12 Correct 253 ms 26544 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 90 ms 8020 KB Output is correct
15 Correct 80 ms 3920 KB Output is correct
16 Correct 1411 ms 26252 KB Output is correct
17 Correct 257 ms 26316 KB Output is correct
18 Correct 277 ms 26188 KB Output is correct
19 Runtime error 450 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -