oj.uz

답안 #1009950

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009950 2024-06-28T08:14:03 Z stdfloat 벽 (IOI14_wall) C++17
61 / 100
 1623 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, (l + r) >> 1, x, y, op, h), upd((nd << 1) + 2, ((l + r) >> 1) + 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);
}

Compilation message

wall.cpp: In function 'int upd(int, int, int, int, int, int, int)':
wall.cpp:55:6: warning: unused variable 'ch' [-Wunused-variable]
   55 |  int ch = (nd << 1) + 1, md = (l + r) >> 1;
      |      ^~
wall.cpp:55:26: warning: unused variable 'md' [-Wunused-variable]
   55 |  int ch = (nd << 1) + 1, md = (l + r) >> 1;
      |                          ^~

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 2276 KB Output is correct
5 Correct 9 ms 2140 KB Output is correct
6 Correct 11 ms 2292 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 72 ms 8172 KB Output is correct
3 Correct 263 ms 6736 KB Output is correct
4 Correct 845 ms 25996 KB Output is correct
5 Correct 273 ms 26452 KB Output is correct
6 Correct 264 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 12 ms 2208 KB Output is correct
5 Correct 7 ms 2136 KB Output is correct
6 Correct 6 ms 2136 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 8020 KB Output is correct
9 Correct 277 ms 6824 KB Output is correct
10 Correct 917 ms 25860 KB Output is correct
11 Correct 259 ms 26452 KB Output is correct
12 Correct 248 ms 26448 KB Output is correct
13 Correct 0 ms 596 KB Output is correct
14 Correct 98 ms 8020 KB Output is correct
15 Correct 66 ms 3936 KB Output is correct
16 Correct 1378 ms 26256 KB Output is correct
17 Correct 248 ms 26196 KB Output is correct
18 Correct 276 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 12 ms 2140 KB Output is correct
5 Correct 11 ms 2136 KB Output is correct
6 Correct 13 ms 2140 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 157 ms 8176 KB Output is correct
9 Correct 261 ms 6736 KB Output is correct
10 Correct 981 ms 25940 KB Output is correct
11 Correct 263 ms 26384 KB Output is correct
12 Correct 261 ms 26408 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 74 ms 8156 KB Output is correct
15 Correct 68 ms 3880 KB Output is correct
16 Correct 1623 ms 26252 KB Output is correct
17 Correct 312 ms 26184 KB Output is correct
18 Correct 290 ms 26228 KB Output is correct
19 Runtime error 455 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -