oj.uz

Submission #966257

# Submission time Handle Problem Language Result Execution time Memory
966257 2024-04-19T15:28:09 Z raspy Wall (IOI14_wall) C++14
100 / 100
 620 ms 107604 KB 
#include "wall.h"
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>

#define inf 1000000

using namespace std;

vector<pair<int, int>> sg(8000005, pair<int, int>(0, inf));
int a[2000005];

void propagate(int vz, int l, int d)
{
	if (l == d)
		return;
	int lv = vz*2+1, ds = vz*2+2;
	sg[lv].first = min(sg[lv].first, sg[vz].second);
	sg[lv].second = min(sg[lv].second, sg[vz].second);
	sg[lv].first = max(sg[lv].first, sg[vz].first);
	sg[lv].second = max(sg[lv].second, sg[vz].first);
	sg[ds].first = min(sg[ds].first, sg[vz].second);
	sg[ds].second = min(sg[ds].second, sg[vz].second);
	sg[ds].first = max(sg[ds].first, sg[vz].first);
	sg[ds].second = max(sg[ds].second, sg[vz].first);
	sg[vz] = {0, inf};
}

void updmn(int vz, int l, int d, int i, int j, int hg)
{
	if (i > d || j < l)
		return;
	propagate(vz, l, d);
	if (i <= l && j >= d)
	{
		sg[vz].first = min(sg[vz].first, hg);
		sg[vz].second = min(sg[vz].second, hg);
		return;
	}
	int mid = (l+d)/2;
	updmn(vz*2+1, l, mid, i, min(mid, j), hg);
	updmn(vz*2+2, mid+1, d, max(mid+1, i), j, hg);
}

void updmx(int vz, int l, int d, int i, int j, int hg)
{
	if (i > d || j < l)
		return;
	if (i <= l && j >= d)
	{
		sg[vz].first = max(sg[vz].first, hg);
		sg[vz].second = max(sg[vz].second, hg);
		return;
	}
	propagate(vz, l, d);
	int mid = (l+d)/2;
	updmx(vz*2+1, l, mid, i, min(mid, j), hg);
	updmx(vz*2+2, mid+1, d, max(mid+1, i), j, hg);
}

void izpis(int vz, int l, int d)
{
	propagate(vz, l, d);
	if (l == d)
	{
		a[l] = sg[vz].first;
		return;
	}
	int mid = (l+d)/2;
	izpis(vz*2+1, l, mid);
	izpis(vz*2+2, mid+1, d);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for (int i = 0; i < k; i++)
	{
		int l = left[i], r = right[i];
		if (op[i] == 2)
			updmn(0, 0, n-1, l, r, height[i]);
		else
			updmx(0, 0, n-1, l, r, height[i]);
	}
	izpis(0, 0, n-1);
	for (int i = 0; i < n; i++)
		finalHeight[i] = a[i];
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 63068 KB Output is correct
2 Correct 15 ms 63136 KB Output is correct
3 Correct 18 ms 63068 KB Output is correct
4 Correct 17 ms 63324 KB Output is correct
5 Correct 17 ms 63324 KB Output is correct
6 Correct 16 ms 63352 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63068 KB Output is correct
2 Correct 123 ms 76608 KB Output is correct
3 Correct 194 ms 68904 KB Output is correct
4 Correct 385 ms 83108 KB Output is correct
5 Correct 244 ms 84132 KB Output is correct
6 Correct 242 ms 82628 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 63032 KB Output is correct
2 Correct 14 ms 63068 KB Output is correct
3 Correct 13 ms 63064 KB Output is correct
4 Correct 18 ms 63324 KB Output is correct
5 Correct 16 ms 63324 KB Output is correct
6 Correct 16 ms 63324 KB Output is correct
7 Correct 13 ms 63080 KB Output is correct
8 Correct 123 ms 76628 KB Output is correct
9 Correct 140 ms 70224 KB Output is correct
10 Correct 390 ms 83416 KB Output is correct
11 Correct 244 ms 84356 KB Output is correct
12 Correct 243 ms 82592 KB Output is correct
13 Correct 13 ms 63064 KB Output is correct
14 Correct 123 ms 76628 KB Output is correct
15 Correct 38 ms 64140 KB Output is correct
16 Correct 387 ms 83600 KB Output is correct
17 Correct 280 ms 82964 KB Output is correct
18 Correct 245 ms 82772 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63068 KB Output is correct
2 Correct 14 ms 63064 KB Output is correct
3 Correct 15 ms 63068 KB Output is correct
4 Correct 19 ms 63332 KB Output is correct
5 Correct 17 ms 63324 KB Output is correct
6 Correct 16 ms 63324 KB Output is correct
7 Correct 13 ms 63068 KB Output is correct
8 Correct 124 ms 76540 KB Output is correct
9 Correct 142 ms 70224 KB Output is correct
10 Correct 384 ms 83288 KB Output is correct
11 Correct 250 ms 84124 KB Output is correct
12 Correct 241 ms 82692 KB Output is correct
13 Correct 13 ms 62876 KB Output is correct
14 Correct 137 ms 76624 KB Output is correct
15 Correct 35 ms 64104 KB Output is correct
16 Correct 380 ms 83360 KB Output is correct
17 Correct 247 ms 82740 KB Output is correct
18 Correct 246 ms 82748 KB Output is correct
19 Correct 620 ms 107604 KB Output is correct
20 Correct 582 ms 104824 KB Output is correct
21 Correct 566 ms 107108 KB Output is correct
22 Correct 568 ms 104676 KB Output is correct
23 Correct 560 ms 104624 KB Output is correct
24 Correct 561 ms 104784 KB Output is correct
25 Correct 572 ms 104732 KB Output is correct
26 Correct 563 ms 107380 KB Output is correct
27 Correct 568 ms 107340 KB Output is correct
28 Correct 574 ms 104784 KB Output is correct
29 Correct 569 ms 104620 KB Output is correct
30 Correct 562 ms 104624 KB Output is correct