oj.uz

Submission #1009947

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

	int ch = (nd << 1) + 1, md = (l + r) >> 1;
	return st[nd] = max(upd((nd << 1) + 1, l, md, x, y, op, h), upd((nd << 1) + 2, 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);
}

Compilation message

wall.cpp: In function 'int upd(int, int, int, int, int, int, int)':
wall.cpp:55:6: warning: unused variable 'ch' [-Wunused-variable]
   55 |  int ch = (nd << 1) + 1, md = (l + r) >> 1;
      |      ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 17 ms 2392 KB Output is correct
5 Correct 8 ms 2140 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 344 KB Output is correct
2 Correct 84 ms 8252 KB Output is correct
3 Correct 280 ms 6736 KB Output is correct
4 Correct 806 ms 25960 KB Output is correct
5 Correct 283 ms 26488 KB Output is correct
6 Correct 231 ms 26532 KB Output is correct

Subtask #3
29.0 / 29.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 13 ms 2256 KB Output is correct
5 Correct 13 ms 2140 KB Output is correct
6 Correct 7 ms 2344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 120 ms 8116 KB Output is correct
9 Correct 278 ms 6736 KB Output is correct
10 Correct 983 ms 25996 KB Output is correct
11 Correct 288 ms 26448 KB Output is correct
12 Correct 261 ms 26468 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 86 ms 8164 KB Output is correct
15 Correct 69 ms 3920 KB Output is correct
16 Correct 1567 ms 26252 KB Output is correct
17 Correct 425 ms 26196 KB Output is correct
18 Correct 271 ms 26120 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 15 ms 2140 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 78 ms 8016 KB Output is correct
9 Correct 287 ms 6872 KB Output is correct
10 Correct 1075 ms 25884 KB Output is correct
11 Correct 346 ms 26420 KB Output is correct
12 Correct 233 ms 26420 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 84 ms 8048 KB Output is correct
15 Correct 66 ms 3920 KB Output is correct
16 Correct 1418 ms 26196 KB Output is correct
17 Correct 284 ms 26192 KB Output is correct
18 Correct 258 ms 26196 KB Output is correct
19 Runtime error 440 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -