oj.uz

Submission #484716

# Submission time Handle Problem Language Result Execution time Memory
484716 2021-11-05T08:58:02 Z WeissBlume Wall (IOI14_wall) C++17
100 / 100
 817 ms 92128 KB 
#include"wall.h"
#include<cstdio>
#include<queue>
#include<memory>
#include<algorithm>
#define x first
#define y second
using namespace std;
using ii = pair<int, int>;
int read(int x = 0) { return scanf("%d", &x), x; }
template<class node_t>
struct LazySegmentTree {
	using T = typename node_t::val_t;
	using U = typename node_t::upd_t;
	unique_ptr<node_t[]> nodes;
	int size, height;

	LazySegmentTree(int n): size(1), height(0) {
		while (size < n || size < 8) size <<= 1, ++height;
		nodes = unique_ptr<node_t[]>(new node_t[size<<1]);

		for (int i = size - 1; i > 0; i--)
			nodes[i].combine(nodes[i<<1], nodes[i<<1|1]);
	}

	void update(int _l, int _r, const U& v) {
		push(_l); push(_r+1);
		for (int l = _l + size, r = _r + size + 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) nodes[l++].update(v);
			if (r & 1) nodes[--r].update(v);
		}

		push(_l); push(_r+1);
		for (int l = (_l+size) >> 1; l > 0; l >>= 1)
			nodes[l].combine(nodes[l<<1], nodes[l<<1|1]);
		for (int r = (_r+size) >> 1; r > 0; r >>= 1)
			nodes[r].combine(nodes[r<<1], nodes[r<<1|1]);
	}

	void push(int p) {
		for (int s = height; s > 0; s--) _push((p + size) >> s);
	}

	void _push(int i) {
		if (nodes[i].has_lazy()) {
			nodes[i<<1].update(nodes[i].lazy);
			nodes[i<<1|1].update(nodes[i].lazy);
			nodes[i].clear_lazy();
		}
	}

	T query(int l, int r) {
		push(l), push(r+1);
		node_t le, ri, tmp;
		for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) le = tmp.combine(le, nodes[l++]);
			if (r & 1) ri = tmp.combine(nodes[--r], ri);
		}
		return tmp.combine(le, ri).query();
	}
};

struct WallNode {
	constexpr static ii lazy_null {0, 100'000};
	using self_t = WallNode;
	using val_t = int;
	using upd_t = ii;
	upd_t lazy{lazy_null};
	upd_t v{};
	val_t query() const { return v.x; }
	void update(upd_t a) {
		if (a.x > v.y) v = ii{a.x, a.x};
		if (a.x > lazy.y) lazy = ii{a.x, a.x};
		if (a.y < v.x) v = ii{a.y, a.y};
		if (a.y < lazy.x) lazy = ii{a.y, a.y};
		lazy.x = max(lazy.x, a.x);
		lazy.y = min(lazy.y, a.y);
		v.x = max(v.x, a.x);
		v.y = min(v.y, a.y);
	}
	bool has_lazy() const { return lazy != lazy_null; }
	void clear_lazy() { lazy = lazy_null; }
	self_t combine(self_t const& le, self_t const& ri) {
		if (le.v != ii{}) v = le.v;
		if (ri.v != ii{}) v = ri.v;
		return *this;
	}
};

// int n = read(), m = read();
// LazySegmentTree<WallNode> tree(n+2);
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	LazySegmentTree<WallNode> tree(n+2);
	for (int i = 0; i < k; i++) switch (op[i]) {
		case 1: {
			int l = left[i]+1, r = right[i]+1, h = height[i];
			tree.update(l, r, ii{h, 100'000});
			break;
		}
		case 2: {
			int l = left[i]+1, r = right[i]+1, h = height[i];
			tree.update(l, r, ii{0, h});
			break;
		}
		default: __builtin_unreachable();
	}
	for (int i = 1; i <= n; i++) finalHeight[i-1] = tree.query(i, i);
}
/*
int main()
{
	for (int l, r, h; m--;) switch(read()) {
		case 1: {
			l = read()+1, r = read()+1, h = read();
			tree.update(l, r, ii{h, 100'000});
			break;
		}
		case 2: {
			l = read()+1, r = read()+1, h = read();
			tree.update(l, r, ii{0, h});
			break;
		}
		default: __builtin_unreachable();
	}
	for (int i = 1; i <= n; i++) printf("%d\n", tree.query(i, i));
	return 0;
}
*/

Compilation message

wall.cpp: In function 'int read(int)':
wall.cpp:10:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | int read(int x = 0) { return scanf("%d", &x), x; }
      |                              ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 420 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 8 ms 972 KB Output is correct
5 Correct 5 ms 992 KB Output is correct
6 Correct 6 ms 972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 178 ms 13992 KB Output is correct
3 Correct 169 ms 8300 KB Output is correct
4 Correct 514 ms 22108 KB Output is correct
5 Correct 330 ms 22772 KB Output is correct
6 Correct 320 ms 21188 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 8 ms 972 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 6 ms 972 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 168 ms 13944 KB Output is correct
9 Correct 216 ms 8472 KB Output is correct
10 Correct 560 ms 22160 KB Output is correct
11 Correct 310 ms 22764 KB Output is correct
12 Correct 284 ms 21204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 178 ms 13884 KB Output is correct
15 Correct 43 ms 2364 KB Output is correct
16 Correct 702 ms 22224 KB Output is correct
17 Correct 293 ms 21612 KB Output is correct
18 Correct 279 ms 21644 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 972 KB Output is correct
5 Correct 6 ms 972 KB Output is correct
6 Correct 5 ms 956 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 159 ms 13916 KB Output is correct
9 Correct 171 ms 8372 KB Output is correct
10 Correct 473 ms 22216 KB Output is correct
11 Correct 265 ms 22768 KB Output is correct
12 Correct 290 ms 21440 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 155 ms 13912 KB Output is correct
15 Correct 38 ms 2380 KB Output is correct
16 Correct 644 ms 22340 KB Output is correct
17 Correct 293 ms 21596 KB Output is correct
18 Correct 298 ms 21748 KB Output is correct
19 Correct 811 ms 92052 KB Output is correct
20 Correct 802 ms 91996 KB Output is correct
21 Correct 817 ms 92056 KB Output is correct
22 Correct 765 ms 91972 KB Output is correct
23 Correct 767 ms 92128 KB Output is correct
24 Correct 756 ms 91972 KB Output is correct
25 Correct 763 ms 92108 KB Output is correct
26 Correct 784 ms 92124 KB Output is correct
27 Correct 778 ms 92084 KB Output is correct
28 Correct 739 ms 92032 KB Output is correct
29 Correct 757 ms 91972 KB Output is correct
30 Correct 760 ms 91972 KB Output is correct