oj.uz

Submission #1009958

# Submission time Handle Problem Language Result Execution time Memory
1009958 2024-06-28T08:15:57 Z stdfloat Wall (IOI14_wall) C++17
61 / 100
 1511 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) {
		for (auto i : lz[nd]) {
			Lz((nd << 1) + 1, i); Lz((nd << 1) + 2, 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 344 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 14 ms 2404 KB Output is correct
5 Correct 7 ms 2396 KB Output is correct
6 Correct 7 ms 2396 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 91 ms 12700 KB Output is correct
3 Correct 289 ms 9828 KB Output is correct
4 Correct 981 ms 33684 KB Output is correct
5 Correct 276 ms 34308 KB Output is correct
6 Correct 280 ms 33432 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 14 ms 2348 KB Output is correct
5 Correct 11 ms 2396 KB Output is correct
6 Correct 8 ms 2220 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 85 ms 12800 KB Output is correct
9 Correct 302 ms 9848 KB Output is correct
10 Correct 987 ms 33680 KB Output is correct
11 Correct 275 ms 34256 KB Output is correct
12 Correct 277 ms 33276 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 93 ms 12816 KB Output is correct
15 Correct 74 ms 4444 KB Output is correct
16 Correct 1511 ms 33936 KB Output is correct
17 Correct 326 ms 33364 KB Output is correct
18 Correct 267 ms 33416 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 14 ms 2396 KB Output is correct
5 Correct 7 ms 2172 KB Output is correct
6 Correct 7 ms 2396 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 75 ms 12628 KB Output is correct
9 Correct 293 ms 9808 KB Output is correct
10 Correct 936 ms 33616 KB Output is correct
11 Correct 273 ms 34372 KB Output is correct
12 Correct 302 ms 33360 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 93 ms 12684 KB Output is correct
15 Correct 75 ms 4528 KB Output is correct
16 Correct 1476 ms 33932 KB Output is correct
17 Correct 285 ms 33348 KB Output is correct
18 Correct 334 ms 33320 KB Output is correct
19 Runtime error 440 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -