oj.uz

Submission #1009873

# Submission time Handle Problem Language Result Execution time Memory
1009873 2024-06-28T07:06:25 Z stdfloat Wall (IOI14_wall) C++17
61 / 100
 1449 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);
	}

	assert((int)lz[nd].size() < 3);
}

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(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

# Verdict Execution time Memory 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 2340 KB Output is correct
5 Correct 8 ms 2396 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 84 ms 13992 KB Output is correct
3 Correct 277 ms 10652 KB Output is correct
4 Correct 937 ms 35596 KB Output is correct
5 Correct 275 ms 36720 KB Output is correct
6 Correct 256 ms 35108 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 572 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 14 ms 2356 KB Output is correct
5 Correct 7 ms 2396 KB Output is correct
6 Correct 7 ms 2276 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 84 ms 13872 KB Output is correct
9 Correct 296 ms 10580 KB Output is correct
10 Correct 970 ms 35804 KB Output is correct
11 Correct 276 ms 36644 KB Output is correct
12 Correct 261 ms 34912 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 86 ms 13920 KB Output is correct
15 Correct 75 ms 4428 KB Output is correct
16 Correct 1449 ms 35848 KB Output is correct
17 Correct 272 ms 35364 KB Output is correct
18 Correct 266 ms 35144 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 15 ms 2396 KB Output is correct
5 Correct 7 ms 2432 KB Output is correct
6 Correct 7 ms 2392 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 89 ms 13876 KB Output is correct
9 Correct 288 ms 10580 KB Output is correct
10 Correct 957 ms 35596 KB Output is correct
11 Correct 304 ms 36664 KB Output is correct
12 Correct 257 ms 35152 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 85 ms 13888 KB Output is correct
15 Correct 77 ms 4436 KB Output is correct
16 Correct 1449 ms 35780 KB Output is correct
17 Correct 280 ms 35152 KB Output is correct
18 Correct 272 ms 35152 KB Output is correct
19 Runtime error 412 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -