oj.uz

Submission #292328

# Submission time Handle Problem Language Result Execution time Memory
292328 2020-09-06T20:41:53 Z VodkaInTheJar Wall (IOI14_wall) C++14
100 / 100
 1052 ms 128888 KB 
#include <bits/stdc++.h>

using namespace std;

struct node
{
	int min_val, max_val;
	int lazy; 
    node() {min_val = max_val = 0, lazy = -1;}
};

const int maxn = 2e6 + 3; 

node tr[maxn * 4]; 
void push(int v, int l, int r)
{
	if (tr[v].lazy == -1)
	return;
	
	tr[v].min_val = tr[v].max_val = tr[v].lazy;
	
	if (l != r)
	tr[v * 2].lazy = tr[v * 2 + 1].lazy = tr[v].lazy;
	
	tr[v].lazy = -1; 
}

void merge(int v)
{
	tr[v].min_val = min(tr[v * 2].min_val, tr[v * 2 + 1].min_val);
	tr[v].max_val = max(tr[v * 2].max_val, tr[v * 2 + 1].max_val);
}

void update(int v, int l, int r, int ll, int rr, int val, bool type)
{
	push(v, l, r);
	if (l > rr || r < ll)
	return;
	
	if (l >= ll && r <= rr)
	{
		if (!type)
		{
			if (val <= tr[v].min_val)
			{
				tr[v].lazy = val;
				push(v, l, r);
				
				return;
			}
			
			else
			if (val >= tr[v].max_val)
			return;
		}
		
		else 
		{
			if (val >= tr[v].max_val)
			{
				tr[v].lazy = val;
				push(v, l, r);
				
				return;
			}
			
			else 
			if (val <= tr[v].min_val)
			return;
		}
	}
	
	int mid = (l + r) / 2;
	update(v * 2, l, mid, ll, rr, val, type);
	update(v * 2 + 1, mid + 1, r, ll, rr, val, type);
	
	merge(v);
}

int get(int v, int l, int r, int pos)
{
	push(v, l, r);
	if (l == r)
	return tr[v].min_val;
	
	int mid = (l + r) / 2;
	if (pos <= mid)
	return get(v * 2, l, mid, pos);
	
	else 
	return get(v * 2 + 1, mid + 1, r, pos);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for (int i = 0; i < k; i++)
	{
		if (op[i] == 1)
		update(1, 1, n, left[i] + 1, right[i] + 1, height[i], true);
		
		else 
		update(1, 1, n, left[i] + 1, right[i] + 1, height[i], false);
	}
	
	for (int i = 1; i <= n; i++)
	finalHeight[i-1] = get(1, 1, n, i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 94200 KB Output is correct
2 Correct 62 ms 94328 KB Output is correct
3 Correct 65 ms 94328 KB Output is correct
4 Correct 71 ms 94456 KB Output is correct
5 Correct 68 ms 94456 KB Output is correct
6 Correct 70 ms 94456 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94316 KB Output is correct
2 Correct 246 ms 107896 KB Output is correct
3 Correct 268 ms 101408 KB Output is correct
4 Correct 669 ms 110348 KB Output is correct
5 Correct 454 ms 110840 KB Output is correct
6 Correct 439 ms 110840 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 94200 KB Output is correct
2 Correct 67 ms 94328 KB Output is correct
3 Correct 64 ms 94332 KB Output is correct
4 Correct 65 ms 94456 KB Output is correct
5 Correct 70 ms 94584 KB Output is correct
6 Correct 70 ms 94504 KB Output is correct
7 Correct 59 ms 94204 KB Output is correct
8 Correct 241 ms 107948 KB Output is correct
9 Correct 305 ms 101368 KB Output is correct
10 Correct 665 ms 110436 KB Output is correct
11 Correct 441 ms 110968 KB Output is correct
12 Correct 425 ms 110968 KB Output is correct
13 Correct 59 ms 94200 KB Output is correct
14 Correct 241 ms 108000 KB Output is correct
15 Correct 102 ms 95480 KB Output is correct
16 Correct 846 ms 110712 KB Output is correct
17 Correct 433 ms 110584 KB Output is correct
18 Correct 439 ms 110584 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94200 KB Output is correct
2 Correct 63 ms 94308 KB Output is correct
3 Correct 67 ms 94328 KB Output is correct
4 Correct 68 ms 94456 KB Output is correct
5 Correct 66 ms 94456 KB Output is correct
6 Correct 66 ms 94456 KB Output is correct
7 Correct 62 ms 94200 KB Output is correct
8 Correct 234 ms 107896 KB Output is correct
9 Correct 258 ms 101496 KB Output is correct
10 Correct 631 ms 110328 KB Output is correct
11 Correct 443 ms 111096 KB Output is correct
12 Correct 422 ms 110840 KB Output is correct
13 Correct 60 ms 94200 KB Output is correct
14 Correct 243 ms 107896 KB Output is correct
15 Correct 105 ms 95480 KB Output is correct
16 Correct 844 ms 110584 KB Output is correct
17 Correct 444 ms 110652 KB Output is correct
18 Correct 439 ms 110584 KB Output is correct
19 Correct 1052 ms 127912 KB Output is correct
20 Correct 1037 ms 126456 KB Output is correct
21 Correct 1044 ms 128888 KB Output is correct
22 Correct 1052 ms 126232 KB Output is correct
23 Correct 1033 ms 126328 KB Output is correct
24 Correct 1041 ms 126344 KB Output is correct
25 Correct 1031 ms 126328 KB Output is correct
26 Correct 1050 ms 128632 KB Output is correct
27 Correct 1051 ms 128716 KB Output is correct
28 Correct 1042 ms 126208 KB Output is correct
29 Correct 1034 ms 126332 KB Output is correct
30 Correct 1033 ms 126396 KB Output is correct