oj.uz

Submission #136213

# Submission time Handle Problem Language Result Execution time Memory
136213 2019-07-25T02:38:42 Z mosesmayer Wall (IOI14_wall) C++17
100 / 100
 1222 ms 162164 KB 
#include "wall.h"
#include <cstdio>
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
typedef long long LL;

const LL LINF = 1000000000LL * 1000000000LL;
const int mxsz = 2e6 + 3;
struct Node{
	LL top, bot;
	Node(){
		top = 0;
		bot = LINF;
	}
	Node operator+ (const Node &r) const{
		Node ret;
		ret.top = max(top, r.top);
		ret.bot = min(bot, r.bot);
		return ret;
	}
};
struct Seg{
	Node st[mxsz << 2];
	void prop(int p, int l, int r){
		if (l == r) return;
		for (int i = (p<<1); i <= (p<<1|1); i++){
			st[i].bot = min(st[i].bot, st[p].bot);
			st[i].bot = max(st[i].bot, st[p].top);
			st[i].top = max(st[i].top, st[p].top);
			st[i].top = min(st[i].top, st[p].bot);
		}
		st[p].top = 0; st[p].bot = LINF;
	}

	void setMax(int i, int j, LL v, int p, int l, int r){
		// remove columns to have at most v bricks
	//	printf("-> %d %d %lld %d %d\n", i, j, v, l, r);
		if (j < l || i > r) return;
		if (i <= l && j >= r){
			st[p].top = min(st[p].top, v);
			st[p].bot = min(st[p].bot, v);
	//		printf("%d %d: %lld %lld\n", l, r, st[p].top, st[p].bot);
			return;
		}
		prop(p, l, r);
		int md = (l + r) >> 1;
		setMax(i, j, v, p<<1, l, md); setMax(i, j, v, p<<1|1, md+1, r);
	//	st[p] = st[p<<1] + st[p<<1|1];
	//	printf("%d %d: %lld %lld\n", l, r, st[p].top, st[p].bot);
	}
	
	void setMin(int i, int j, LL v, int p, int l, int r){
		// add to columns to have at least v bricks
	//	printf("-> %d %d %lld %d %d\n", i, j, v, l, r);
		if (j < l || i > r) return;
		if (i <= l && j >= r){
			st[p].top = max(st[p].top, v);
			st[p].bot = max(st[p].bot, v);
	//		printf("%d %d: %lld %lld\n", l, r, st[p].top, st[p].bot);
			return;
		}
		prop(p, l, r);
		int md = (l + r) >> 1;
		setMin(i, j, v, p<<1, l, md); setMin(i, j, v, p<<1|1, md+1, r);
	//	st[p] = st[p<<1] + st[p<<1|1];
	//	printf("%d %d: %lld %lld\n", l, r, st[p].top, st[p].bot);
	}

	inline LL get(int i, int p, int l, int r){
		if (l == r){
	//		printf("%d %d:  %lld %lld - - - \n", l, r, st[p].top, st[p].bot);
			return min(st[p].top, st[p].bot);
		}
		prop(p, l, r);
		int md = (l + r) >> 1;
		if (i <= md) return get(i, p<<1, l, md);
		return get(i, p<<1|1, md+1, r);
	}	
} seg;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < k; i++){
	//	printf("%d %d %lld %lld\n", op[i], left[i], right[i], height[i]);
		if (op[i] == 1){
			seg.setMin(left[i], right[i], height[i], 1, 0, n-1);
		} else {
			seg.setMax(left[i], right[i], height[i], 1, 0, n-1);
		}
	//	puts("");
	}
	for (int i = 0; i < n; i++){
		finalHeight[i] = seg.get(i, 1, 0, n-1);
	}
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 125560 KB Output is correct
2 Correct 102 ms 125692 KB Output is correct
3 Correct 101 ms 125560 KB Output is correct
4 Correct 107 ms 125816 KB Output is correct
5 Correct 106 ms 125816 KB Output is correct
6 Correct 107 ms 125816 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 125468 KB Output is correct
2 Correct 276 ms 139172 KB Output is correct
3 Correct 310 ms 132856 KB Output is correct
4 Correct 698 ms 143608 KB Output is correct
5 Correct 448 ms 144584 KB Output is correct
6 Correct 445 ms 143224 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 125632 KB Output is correct
2 Correct 102 ms 125732 KB Output is correct
3 Correct 102 ms 125564 KB Output is correct
4 Correct 108 ms 125864 KB Output is correct
5 Correct 107 ms 125828 KB Output is correct
6 Correct 107 ms 125736 KB Output is correct
7 Correct 101 ms 125560 KB Output is correct
8 Correct 274 ms 139144 KB Output is correct
9 Correct 307 ms 132728 KB Output is correct
10 Correct 701 ms 143608 KB Output is correct
11 Correct 449 ms 144928 KB Output is correct
12 Correct 441 ms 143096 KB Output is correct
13 Correct 122 ms 125560 KB Output is correct
14 Correct 275 ms 139256 KB Output is correct
15 Correct 137 ms 126712 KB Output is correct
16 Correct 733 ms 143992 KB Output is correct
17 Correct 450 ms 143352 KB Output is correct
18 Correct 446 ms 143280 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 125560 KB Output is correct
2 Correct 123 ms 125688 KB Output is correct
3 Correct 112 ms 125676 KB Output is correct
4 Correct 133 ms 125884 KB Output is correct
5 Correct 107 ms 125816 KB Output is correct
6 Correct 107 ms 125816 KB Output is correct
7 Correct 101 ms 125560 KB Output is correct
8 Correct 274 ms 139316 KB Output is correct
9 Correct 305 ms 132728 KB Output is correct
10 Correct 742 ms 143736 KB Output is correct
11 Correct 448 ms 144760 KB Output is correct
12 Correct 441 ms 143136 KB Output is correct
13 Correct 101 ms 125560 KB Output is correct
14 Correct 283 ms 139320 KB Output is correct
15 Correct 137 ms 126824 KB Output is correct
16 Correct 728 ms 143864 KB Output is correct
17 Correct 449 ms 143336 KB Output is correct
18 Correct 450 ms 143348 KB Output is correct
19 Correct 1213 ms 162164 KB Output is correct
20 Correct 1200 ms 159488 KB Output is correct
21 Correct 1205 ms 162044 KB Output is correct
22 Correct 1212 ms 159412 KB Output is correct
23 Correct 1202 ms 159376 KB Output is correct
24 Correct 1201 ms 159548 KB Output is correct
25 Correct 1198 ms 159352 KB Output is correct
26 Correct 1222 ms 162020 KB Output is correct
27 Correct 1222 ms 162072 KB Output is correct
28 Correct 1207 ms 159636 KB Output is correct
29 Correct 1202 ms 159608 KB Output is correct
30 Correct 1202 ms 159648 KB Output is correct