oj.uz

Submission #416131

# Submission time Handle Problem Language Result Execution time Memory
416131 2021-06-02T05:01:56 Z xyzyzl Wall (IOI14_wall) C++14
100 / 100
 1267 ms 93868 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e6+5;
const int INF  = 1e9+7;
int n, arr[MAXN], st[4*MAXN], lz1[4*MAXN], lz2[4*MAXN];

void upd(int node, int a, int b, int mn, int mx, int l, int r)
{
	if(l == a && r == b)
	{
		st[node] = max(st[node], mx);
		st[node] = min(st[node], mn);
		if(mx > lz1[node])
		{
			lz1[node] = lz2[node] = mx;
		} else if(mn < lz2[node])
		{
			lz1[node] = lz2[node] = mn;
		} else 
		{
			lz1[node] = min(lz1[node], mn);
			lz2[node] = max(lz2[node], mx);
		}
		return;
	}
	int mid = (l+r)/2;
	// nothing that could go wrong here, this is just checking the smaller intervals
	// individually with no deeper recursion
	upd(2*node, l, mid, lz1[node], lz2[node], l, mid);
	upd(2*node+1, mid+1, r, lz1[node], lz2[node], mid+1, r);
	lz1[node] = INF;
	lz2[node] = 0;
	// here is what is wrong
	// we are cutting our current interval into intervals based on mid, and then 
	// we process updates for each interval
	if(b <= mid)
	{
		upd(2*node, a, b, mn, mx, l, mid);
	} else if(a > mid)
	{
		upd(2*node+1, a, b, mn, mx, mid+1, r);
	} else 
	{
		upd(2*node, a, mid, mn, mx, l, mid);
		upd(2*node+1, mid+1, b, mn, mx, mid+1, r);
	}
	st[node] = min(st[2*node], st[2*node+1]);
}

void build(int node, int l, int r)
{
	if(l == r)
	{
		lz1[node] = INF;
		return;
	}
	int mid = (l+r)/2;
	build(node*2, l, mid);
	build(node*2+1, mid+1, r);
	lz1[node] = INF;
}

void convert(int node, int l, int r)
{
	if(l == r)
	{
		arr[l] = st[node];		
		return;
	}
	int mid = (l+r)/2;
	upd(2*node, l, mid, lz1[node], lz2[node], l, mid);
	upd(2*node+1, mid+1, r, lz1[node], lz2[node], mid+1, r);
	lz1[node] = INF;
	lz2[node] = 0;

	convert(2*node, l, mid);
	convert(2*node+1, mid+1, r);
}

void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	n = _n;
	build(1, 0, n-1);
	// perform updates for each query.
	for(int i = 0; i < k; i++)
	{
		if(op[i] == 1)
		{
			upd(1, left[i], right[i], INF, height[i], 0, n-1);
		} else 
		{
			upd(1, left[i], right[i], height[i], 0, 0, n-1);
		}
	}
	convert(1, 0, n-1);
	for(int i = 0; i < n; i++) finalHeight[i] = arr[i];
}

/*
int main()
{
	int op[6] = {1,2,2,1,1,2};
	int left[6] = {1,4,3,0,2,6};
	int right[6] = {8,9,6,5,2,7};
	int height[6] = {4,1,5,3,5,0};
	int finalHeight[10] = {0,0,0,0,0,0,0,0,0,0};
	buildWall(10, 6, op, left, right, height, finalHeight);
	for(int i = 0; i < 10; i++)
	{
		cout << finalHeight[i] << " ";
	}
}
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 8 ms 972 KB Output is correct
5 Correct 7 ms 892 KB Output is correct
6 Correct 8 ms 960 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 162 ms 13892 KB Output is correct
3 Correct 255 ms 8232 KB Output is correct
4 Correct 764 ms 21744 KB Output is correct
5 Correct 477 ms 22876 KB Output is correct
6 Correct 444 ms 21248 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 972 KB Output is correct
5 Correct 8 ms 952 KB Output is correct
6 Correct 8 ms 996 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 156 ms 13952 KB Output is correct
9 Correct 257 ms 8356 KB Output is correct
10 Correct 754 ms 21816 KB Output is correct
11 Correct 470 ms 22860 KB Output is correct
12 Correct 458 ms 21304 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 166 ms 13940 KB Output is correct
15 Correct 46 ms 2268 KB Output is correct
16 Correct 845 ms 22084 KB Output is correct
17 Correct 453 ms 21444 KB Output is correct
18 Correct 461 ms 21524 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 980 KB Output is correct
5 Correct 8 ms 972 KB Output is correct
6 Correct 7 ms 972 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 163 ms 13900 KB Output is correct
9 Correct 252 ms 8320 KB Output is correct
10 Correct 743 ms 21768 KB Output is correct
11 Correct 467 ms 22812 KB Output is correct
12 Correct 471 ms 21268 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 167 ms 13884 KB Output is correct
15 Correct 47 ms 2244 KB Output is correct
16 Correct 849 ms 22080 KB Output is correct
17 Correct 491 ms 21504 KB Output is correct
18 Correct 486 ms 21520 KB Output is correct
19 Correct 1267 ms 93828 KB Output is correct
20 Correct 1189 ms 91204 KB Output is correct
21 Correct 1240 ms 93716 KB Output is correct
22 Correct 1187 ms 91316 KB Output is correct
23 Correct 1198 ms 91244 KB Output is correct
24 Correct 1196 ms 91332 KB Output is correct
25 Correct 1219 ms 91248 KB Output is correct
26 Correct 1204 ms 93868 KB Output is correct
27 Correct 1203 ms 93708 KB Output is correct
28 Correct 1205 ms 91332 KB Output is correct
29 Correct 1204 ms 91236 KB Output is correct
30 Correct 1225 ms 91204 KB Output is correct