oj.uz

Submission #235617

# Submission time Handle Problem Language Result Execution time Memory
235617 2020-05-28T20:28:03 Z luciocf Wall (IOI14_wall) C++14
100 / 100
 1028 ms 130756 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

const int maxn = 2e6+10;

struct Node
{
	int mx, mn;
	int lazy;

	Node()
	{
		mx = mn = 0;
		lazy = -1;
	}
} tree[4*maxn];

void flush(int node, int l, int r)
{
	if (tree[node].lazy == -1) return;

	if (l != r)
		tree[2*node].lazy = tree[2*node+1].lazy = tree[node].lazy;

	tree[node].mn = tree[node].mx = tree[node].lazy;

	tree[node].lazy = -1;
}

void upd(int node, int l, int r, int a, int b, int h, int op)
{
	flush(node, l, r);
	if (l > b || r < a) return;

	if (l >= a && r <= b && tree[node].mn == tree[node].mx)
	{
		if (op == 1 && tree[node].mn >= h) return;
		if (op == 2 && tree[node].mn <= h) return;

		tree[node].lazy = h;

		flush(node, l, r);
		return;
	}

	int mid = (l+r)>>1;

	upd(2*node, l, mid, a, b, h, op); upd(2*node+1, mid+1, r, a, b, h, op);

	tree[node].mx = max(tree[2*node].mx, tree[2*node+1].mx);
	tree[node].mn = min(tree[2*node].mn, tree[2*node+1].mn);
}

int query(int node, int l, int r, int pos)
{
	flush(node, l, r);
	if (l == r) return tree[node].mn;

	int mid = (l+r)>>1;

	if (pos <= mid) return query(2*node, l, mid, pos);
	return query(2*node+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++)
		upd(1, 1, n, left[i]+1, right[i]+1, height[i], op[i]);

	for (int i = 1; i <= n; i++)
		finalHeight[i-1] = query(1, 1, n, i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94328 KB Output is correct
2 Correct 55 ms 94328 KB Output is correct
3 Correct 55 ms 94344 KB Output is correct
4 Correct 65 ms 94456 KB Output is correct
5 Correct 61 ms 94584 KB Output is correct
6 Correct 59 ms 94456 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94200 KB Output is correct
2 Correct 228 ms 107872 KB Output is correct
3 Correct 307 ms 101356 KB Output is correct
4 Correct 747 ms 112376 KB Output is correct
5 Correct 388 ms 113404 KB Output is correct
6 Correct 382 ms 111736 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94328 KB Output is correct
2 Correct 55 ms 94328 KB Output is correct
3 Correct 57 ms 94328 KB Output is correct
4 Correct 62 ms 94456 KB Output is correct
5 Correct 60 ms 94456 KB Output is correct
6 Correct 60 ms 94456 KB Output is correct
7 Correct 54 ms 94200 KB Output is correct
8 Correct 225 ms 108024 KB Output is correct
9 Correct 308 ms 101368 KB Output is correct
10 Correct 738 ms 112252 KB Output is correct
11 Correct 385 ms 113376 KB Output is correct
12 Correct 382 ms 111864 KB Output is correct
13 Correct 54 ms 94328 KB Output is correct
14 Correct 223 ms 108024 KB Output is correct
15 Correct 107 ms 95480 KB Output is correct
16 Correct 1028 ms 112752 KB Output is correct
17 Correct 387 ms 111992 KB Output is correct
18 Correct 401 ms 111992 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94200 KB Output is correct
2 Correct 55 ms 94432 KB Output is correct
3 Correct 55 ms 94328 KB Output is correct
4 Correct 63 ms 94456 KB Output is correct
5 Correct 62 ms 94456 KB Output is correct
6 Correct 59 ms 94456 KB Output is correct
7 Correct 53 ms 94328 KB Output is correct
8 Correct 218 ms 107896 KB Output is correct
9 Correct 304 ms 101496 KB Output is correct
10 Correct 760 ms 112336 KB Output is correct
11 Correct 386 ms 113400 KB Output is correct
12 Correct 375 ms 111736 KB Output is correct
13 Correct 54 ms 94328 KB Output is correct
14 Correct 226 ms 107900 KB Output is correct
15 Correct 116 ms 95608 KB Output is correct
16 Correct 1012 ms 112632 KB Output is correct
17 Correct 394 ms 112120 KB Output is correct
18 Correct 405 ms 111968 KB Output is correct
19 Correct 941 ms 130756 KB Output is correct
20 Correct 930 ms 128160 KB Output is correct
21 Correct 935 ms 130680 KB Output is correct
22 Correct 924 ms 128120 KB Output is correct
23 Correct 946 ms 128248 KB Output is correct
24 Correct 928 ms 128120 KB Output is correct
25 Correct 935 ms 128120 KB Output is correct
26 Correct 947 ms 130680 KB Output is correct
27 Correct 946 ms 130680 KB Output is correct
28 Correct 941 ms 128248 KB Output is correct
29 Correct 936 ms 128248 KB Output is correct
30 Correct 922 ms 128248 KB Output is correct