oj.uz

답안 #1009935

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

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

int ch, md;

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) {
		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(ch, 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 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 13 ms 2140 KB Output is correct
5 Correct 6 ms 2140 KB Output is correct
6 Correct 7 ms 2268 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 99 ms 8016 KB Output is correct
3 Correct 267 ms 6872 KB Output is correct
4 Correct 906 ms 25932 KB Output is correct
5 Correct 244 ms 26452 KB Output is correct
6 Correct 251 ms 26452 KB Output is correct

Subtask #3
29.0 / 29.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 13 ms 2140 KB Output is correct
5 Correct 7 ms 2136 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 86 ms 8060 KB Output is correct
9 Correct 269 ms 6740 KB Output is correct
10 Correct 903 ms 25876 KB Output is correct
11 Correct 287 ms 26340 KB Output is correct
12 Correct 267 ms 26452 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 73 ms 8112 KB Output is correct
15 Correct 76 ms 3924 KB Output is correct
16 Correct 1369 ms 26252 KB Output is correct
17 Correct 267 ms 26196 KB Output is correct
18 Correct 272 ms 26196 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 2140 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 7 ms 2140 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 76 ms 8188 KB Output is correct
9 Correct 276 ms 6740 KB Output is correct
10 Correct 836 ms 25996 KB Output is correct
11 Correct 256 ms 26448 KB Output is correct
12 Correct 254 ms 26448 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 84 ms 8048 KB Output is correct
15 Correct 76 ms 3920 KB Output is correct
16 Correct 1390 ms 26096 KB Output is correct
17 Correct 263 ms 26236 KB Output is correct
18 Correct 250 ms 26192 KB Output is correct
19 Runtime error 402 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -