oj.uz

Submission #380605

# Submission time Handle Problem Language Result Execution time Memory
380605 2021-03-22T12:42:10 Z wind_reaper Wall (IOI14_wall) C++17
100 / 100
 721 ms 60012 KB 
#include <bits/stdc++.h>

using namespace std;

void wssert(bool x){
	if(!x){
		cout << "rte\n";
	}
}

struct SegmentTree{
	struct Node{
		int mx, mn;
	};

	vector<Node> tree;
	vector<bool> lazy;
	int sz = 1, N;

	SegmentTree(int n){
		N = n;
		while(sz < n)
			sz <<= 1;
		tree.resize(2*sz, {1000000, 0});
		lazy.resize(2*sz, false);
	}

	Node merge(Node x, Node c){
		if(x.mn >= c.mx) return {x.mn, x.mn};
		if(x.mx <= c.mn) return {x.mx, x.mx};
		return {min(x.mx, c.mx), max(x.mn, c.mn)};
	}

	inline int lc(int x) { return 2*x+1; }
	inline int rc(int x) { return 2*x+2; }

	void push(int x){
		lazy[x] = false;
		wssert(lc(x) < 2*sz);
		wssert(rc(x) < 2*sz);
		lazy[lc(x)] = lazy[rc(x)] = true;
		tree[lc(x)] = merge(tree[x], tree[lc(x)]);
		tree[rc(x)] = merge(tree[x], tree[rc(x)]);
		tree[x] = {1000000, 0};
	}

	void update(int l, int r, int t, int val, int x, int lx, int rx){
		if(rx <= l || lx >= r)
			return;

		if(lx >= l && rx <= r){
			lazy[x] = true;
			if(t == 0) tree[x] = {max(tree[x].mx, val), max(tree[x].mn, val)};
			else tree[x] = {min(tree[x].mx, val), min(tree[x].mn, val)};
			return;
		}

		if(lazy[x]) 
			push(x);

		int mid = (lx + rx) >> 1;
		
		update(l, r, t, val, lc(x), lx, mid);
		update(l, r, t, val, rc(x), mid, rx);
	}

	void construct(int x, int lx, int rx, int ans[]){
		if(rx - lx == 1){
			if(lx < N) ans[lx] = tree[x].mn;
			return;
		}

		int mid = (lx + rx) >> 1;
		
		if(lazy[x])
			push(x);

		wssert(lc(x) < 2*sz);
		wssert(rc(x) < 2*sz);
		
		construct(lc(x), lx, mid, ans);
		construct(rc(x), mid, rx, ans);
	}

	void update(int l, int r, int t, int val) { update(l, r, t, val, 0, 0, sz); }
	void construct(int ans[]){ construct(0, 0, sz, ans); }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegmentTree S(n);
	for(int i = 0; i < k; i++)
		S.update(left[i], right[i] + 1, op[i] - 1, height[i]);
	S.construct(finalHeight);
}

/*int main(){
	int n, k;
	cin >> n >> k;
	int op[k], left[k], right[k], height[k], finalHeight[n];

	for(int i = 0; i < k; i++)
		cin >> op[i] >> left[i] >> right[i] >> height[i];

	buildWall(n, k, op, left, right, height, finalHeight);
	for(int i = 0; i < n; i++)
		cout << finalHeight[i] << ' ';
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 748 KB Output is correct
5 Correct 6 ms 748 KB Output is correct
6 Correct 5 ms 748 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 158 ms 8332 KB Output is correct
3 Correct 200 ms 4236 KB Output is correct
4 Correct 605 ms 20332 KB Output is correct
5 Correct 295 ms 20956 KB Output is correct
6 Correct 276 ms 19308 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 748 KB Output is correct
5 Correct 5 ms 748 KB Output is correct
6 Correct 5 ms 748 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 158 ms 13932 KB Output is correct
9 Correct 201 ms 7916 KB Output is correct
10 Correct 573 ms 20204 KB Output is correct
11 Correct 279 ms 20844 KB Output is correct
12 Correct 275 ms 19180 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 164 ms 14060 KB Output is correct
15 Correct 39 ms 1900 KB Output is correct
16 Correct 712 ms 20332 KB Output is correct
17 Correct 281 ms 19692 KB Output is correct
18 Correct 282 ms 19692 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 8 ms 748 KB Output is correct
5 Correct 5 ms 748 KB Output is correct
6 Correct 5 ms 748 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 161 ms 13932 KB Output is correct
9 Correct 201 ms 8048 KB Output is correct
10 Correct 580 ms 20204 KB Output is correct
11 Correct 279 ms 20844 KB Output is correct
12 Correct 272 ms 19308 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 160 ms 13932 KB Output is correct
15 Correct 39 ms 2028 KB Output is correct
16 Correct 705 ms 20204 KB Output is correct
17 Correct 285 ms 19948 KB Output is correct
18 Correct 282 ms 19692 KB Output is correct
19 Correct 721 ms 59800 KB Output is correct
20 Correct 711 ms 59852 KB Output is correct
21 Correct 704 ms 59768 KB Output is correct
22 Correct 704 ms 59912 KB Output is correct
23 Correct 704 ms 59868 KB Output is correct
24 Correct 702 ms 59800 KB Output is correct
25 Correct 706 ms 60012 KB Output is correct
26 Correct 706 ms 59960 KB Output is correct
27 Correct 705 ms 59948 KB Output is correct
28 Correct 704 ms 59956 KB Output is correct
29 Correct 702 ms 59800 KB Output is correct
30 Correct 707 ms 59784 KB Output is correct