oj.uz

Submission #990148

# Submission time Handle Problem Language Result Execution time Memory
990148 2024-05-29T17:09:30 Z stdfloat Wall (IOI14_wall) C++17
61 / 100
 1520 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() == 1) return;
	if ((int)lz[nd].size() == 2) {
		if (lz[nd][0].ff == 2) lz[nd][0].ss = max(lz[nd][0].ss, lz[nd][1].ss);
		else lz[nd][0].ss = min(lz[nd][0].ss, lz[nd][1].ss);
	}
	else assert(false);
}

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 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 14 ms 2276 KB Output is correct
5 Correct 7 ms 2084 KB Output is correct
6 Correct 7 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 88 ms 8300 KB Output is correct
3 Correct 295 ms 6996 KB Output is correct
4 Correct 932 ms 25936 KB Output is correct
5 Correct 264 ms 26464 KB Output is correct
6 Correct 264 ms 26452 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 344 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 2140 KB Output is correct
6 Correct 7 ms 2136 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 82 ms 8020 KB Output is correct
9 Correct 294 ms 6740 KB Output is correct
10 Correct 948 ms 26036 KB Output is correct
11 Correct 284 ms 26400 KB Output is correct
12 Correct 259 ms 26452 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 83 ms 8144 KB Output is correct
15 Correct 74 ms 3868 KB Output is correct
16 Correct 1438 ms 26192 KB Output is correct
17 Correct 280 ms 26196 KB Output is correct
18 Correct 272 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 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 14 ms 2136 KB Output is correct
5 Correct 7 ms 2136 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 8020 KB Output is correct
9 Correct 294 ms 6828 KB Output is correct
10 Correct 916 ms 25996 KB Output is correct
11 Correct 270 ms 26704 KB Output is correct
12 Correct 258 ms 26536 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 83 ms 8108 KB Output is correct
15 Correct 74 ms 3824 KB Output is correct
16 Correct 1520 ms 26196 KB Output is correct
17 Correct 276 ms 26192 KB Output is correct
18 Correct 273 ms 26188 KB Output is correct
19 Runtime error 379 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -