oj.uz

Submission #1009952

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

	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 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 14 ms 2244 KB Output is correct
5 Correct 7 ms 2136 KB Output is correct
6 Correct 6 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 143 ms 8012 KB Output is correct
3 Correct 298 ms 6928 KB Output is correct
4 Correct 991 ms 26000 KB Output is correct
5 Correct 262 ms 26404 KB Output is correct
6 Correct 239 ms 26372 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 1 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 14 ms 2244 KB Output is correct
5 Correct 10 ms 2140 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 156 ms 8032 KB Output is correct
9 Correct 287 ms 6736 KB Output is correct
10 Correct 899 ms 25940 KB Output is correct
11 Correct 236 ms 26456 KB Output is correct
12 Correct 249 ms 26460 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 71 ms 8176 KB Output is correct
15 Correct 65 ms 3924 KB Output is correct
16 Correct 1319 ms 26192 KB Output is correct
17 Correct 280 ms 26200 KB Output is correct
18 Correct 250 ms 26192 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 2 ms 348 KB Output is correct
4 Correct 12 ms 2268 KB Output is correct
5 Correct 7 ms 2140 KB Output is correct
6 Correct 6 ms 2084 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 78 ms 8152 KB Output is correct
9 Correct 317 ms 6744 KB Output is correct
10 Correct 887 ms 25880 KB Output is correct
11 Correct 245 ms 26356 KB Output is correct
12 Correct 262 ms 26336 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 83 ms 8240 KB Output is correct
15 Correct 75 ms 3888 KB Output is correct
16 Correct 1461 ms 26092 KB Output is correct
17 Correct 281 ms 26100 KB Output is correct
18 Correct 276 ms 26256 KB Output is correct
19 Runtime error 477 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -