oj.uz

Submission #1009933

# Submission time Handle Problem Language Result Execution time Memory
1009933 2024-06-28T08:07:49 Z stdfloat Wall (IOI14_wall) C++17
61 / 100
 1524 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) {
		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 0 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 2224 KB Output is correct
5 Correct 7 ms 2140 KB Output is correct
6 Correct 8 ms 2140 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 83 ms 8140 KB Output is correct
3 Correct 288 ms 6736 KB Output is correct
4 Correct 924 ms 26064 KB Output is correct
5 Correct 256 ms 26448 KB Output is correct
6 Correct 266 ms 26420 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 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 15 ms 2244 KB Output is correct
5 Correct 7 ms 2140 KB Output is correct
6 Correct 9 ms 2184 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 82 ms 8192 KB Output is correct
9 Correct 290 ms 6724 KB Output is correct
10 Correct 911 ms 25864 KB Output is correct
11 Correct 264 ms 26704 KB Output is correct
12 Correct 253 ms 26320 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 90 ms 8172 KB Output is correct
15 Correct 79 ms 3920 KB Output is correct
16 Correct 1524 ms 26256 KB Output is correct
17 Correct 286 ms 26196 KB Output is correct
18 Correct 286 ms 26200 KB Output is correct

Subtask #4
0 / 39.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 20 ms 2252 KB Output is correct
5 Correct 7 ms 2368 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 85 ms 8220 KB Output is correct
9 Correct 318 ms 6884 KB Output is correct
10 Correct 1095 ms 26024 KB Output is correct
11 Correct 291 ms 26452 KB Output is correct
12 Correct 264 ms 26348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 111 ms 8072 KB Output is correct
15 Correct 72 ms 3924 KB Output is correct
16 Correct 1424 ms 26136 KB Output is correct
17 Correct 246 ms 26092 KB Output is correct
18 Correct 260 ms 26328 KB Output is correct
19 Runtime error 409 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -