oj.uz

Submission #1009956

# Submission time Handle Problem Language Result Execution time Memory
1009956 2024-06-28T08:15:21 Z stdfloat Wall (IOI14_wall) C++17
61 / 100
 1472 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];
	}

	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];

	return max(fnd((nd << 1) + 1, l, (l + r) >> 1, x), fnd((nd << 1) + 2, ((l + r) >> 1) + 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 17 ms 2252 KB Output is correct
5 Correct 6 ms 2140 KB Output is correct
6 Correct 8 ms 2272 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 80 ms 8160 KB Output is correct
3 Correct 332 ms 6900 KB Output is correct
4 Correct 1181 ms 25852 KB Output is correct
5 Correct 301 ms 26436 KB Output is correct
6 Correct 287 ms 26548 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 12 ms 2336 KB Output is correct
5 Correct 10 ms 2336 KB Output is correct
6 Correct 8 ms 2324 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 86 ms 8016 KB Output is correct
9 Correct 333 ms 6740 KB Output is correct
10 Correct 1284 ms 25928 KB Output is correct
11 Correct 318 ms 26512 KB Output is correct
12 Correct 402 ms 26444 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 107 ms 8128 KB Output is correct
15 Correct 75 ms 3892 KB Output is correct
16 Correct 1472 ms 26180 KB Output is correct
17 Correct 269 ms 26196 KB Output is correct
18 Correct 282 ms 26192 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 352 KB Output is correct
4 Correct 14 ms 2248 KB Output is correct
5 Correct 6 ms 2292 KB Output is correct
6 Correct 7 ms 2140 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 81 ms 8244 KB Output is correct
9 Correct 277 ms 6996 KB Output is correct
10 Correct 868 ms 26192 KB Output is correct
11 Correct 254 ms 26460 KB Output is correct
12 Correct 263 ms 26368 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 84 ms 8172 KB Output is correct
15 Correct 78 ms 3924 KB Output is correct
16 Correct 1344 ms 26248 KB Output is correct
17 Correct 252 ms 26160 KB Output is correct
18 Correct 253 ms 26196 KB Output is correct
19 Runtime error 420 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -