oj.uz

Submission #239006

# Submission time Handle Problem Language Result Execution time Memory
239006 2020-06-14T03:24:03 Z T0p_ Wall (IOI14_wall) C++14
100 / 100
 768 ms 110456 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define N 2000002

int mx[N<<2], mn[N<<2], tmp[N];
pair<int, int> laz[N<<2];

void push_lazy(int idx, int l, int r)
{
	if(laz[idx].first)
	{
		mx[idx] = mn[idx] = laz[idx].second;
		if(l != r) laz[idx<<1] = laz[idx<<1|1] = laz[idx];
		laz[idx] = {0, 0};
	}
}

void upd_mx(int idx, int l, int r, int a, int b, int h)
{
	push_lazy(idx, l, r);
	if(r < a || b < l || mn[idx] >= h) return ;
	if(a <= l && r <= b && mx[idx] <= h)
	{
		laz[idx] = {1, h};
		push_lazy(idx, l, r);
		return ;
	}
	int mid = (l+r)>>1;
	upd_mx(idx<<1, l, mid, a, b, h), upd_mx(idx<<1|1, mid+1, r, a, b, h);
	mx[idx] = max(mx[idx<<1], mx[idx<<1|1]);
}

void upd_mn(int idx, int l, int r, int a, int b, int h)
{
	push_lazy(idx, l, r);
	if(r < a || b < l || mx[idx] <= h) return ;
	if(a <= l && r <= b && mn[idx] >= h)
	{
		laz[idx] = {2, h};
		push_lazy(idx, l, r);
		return ;
	}
	int mid = (l+r)>>1;
	upd_mn(idx<<1, l, mid, a, b, h), upd_mn(idx<<1|1, mid+1, r, a, b, h);
	mn[idx] = min(mn[idx<<1], mn[idx<<1|1]);
}

void print(int idx, int l, int r)
{
	push_lazy(idx, l, r);
	if(l == r) return void(tmp[l] = mx[idx]);
	int mid = (l+r)>>1;
	print(idx<<1, l, mid), print(idx<<1|1, mid+1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int i=0 ; i<k ; i++)
	{
		switch(op[i])
		{
			case 1: upd_mx(1, 0, n-1, left[i], right[i], height[i]); break;
			case 2: upd_mn(1, 0, n-1, left[i], right[i], height[i]); break;
		}
	}
	print(1, 0, n-1);
	for(int i=0 ; i<n ; i++)
		finalHeight[i] = tmp[i];
  	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 11 ms 1152 KB Output is correct
5 Correct 9 ms 1152 KB Output is correct
6 Correct 10 ms 1152 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 180 ms 13968 KB Output is correct
3 Correct 110 ms 8696 KB Output is correct
4 Correct 260 ms 22904 KB Output is correct
5 Correct 225 ms 23928 KB Output is correct
6 Correct 264 ms 22456 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 11 ms 1152 KB Output is correct
5 Correct 9 ms 1152 KB Output is correct
6 Correct 11 ms 1152 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 176 ms 14072 KB Output is correct
9 Correct 109 ms 8568 KB Output is correct
10 Correct 253 ms 22908 KB Output is correct
11 Correct 229 ms 24056 KB Output is correct
12 Correct 258 ms 22392 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 178 ms 14056 KB Output is correct
15 Correct 38 ms 2680 KB Output is correct
16 Correct 585 ms 23288 KB Output is correct
17 Correct 328 ms 22648 KB Output is correct
18 Correct 326 ms 22520 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 11 ms 1152 KB Output is correct
5 Correct 10 ms 1152 KB Output is correct
6 Correct 10 ms 1152 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 177 ms 13944 KB Output is correct
9 Correct 111 ms 8568 KB Output is correct
10 Correct 271 ms 22844 KB Output is correct
11 Correct 219 ms 23928 KB Output is correct
12 Correct 249 ms 22392 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 179 ms 13944 KB Output is correct
15 Correct 37 ms 2680 KB Output is correct
16 Correct 568 ms 23160 KB Output is correct
17 Correct 321 ms 22648 KB Output is correct
18 Correct 317 ms 22624 KB Output is correct
19 Correct 768 ms 110200 KB Output is correct
20 Correct 729 ms 107900 KB Output is correct
21 Correct 737 ms 110216 KB Output is correct
22 Correct 757 ms 107772 KB Output is correct
23 Correct 729 ms 107768 KB Output is correct
24 Correct 717 ms 107820 KB Output is correct
25 Correct 724 ms 107724 KB Output is correct
26 Correct 735 ms 110328 KB Output is correct
27 Correct 731 ms 110456 KB Output is correct
28 Correct 754 ms 107768 KB Output is correct
29 Correct 755 ms 107784 KB Output is correct
30 Correct 751 ms 107876 KB Output is correct