oj.uz

Submission #122831

# Submission time Handle Problem Language Result Execution time Memory
122831 2019-06-29T10:48:32 Z turbat Wall (IOI14_wall) C++14
100 / 100
 803 ms 82100 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define N 2000005

int lim[4 * N], seg[4 * N], h[N];

void clear(int nd){
	seg[nd * 2] = max(seg[nd * 2], min(lim[nd * 2], seg[nd]));
	seg[nd * 2 + 1] = max(seg[nd * 2 + 1], min(lim[nd * 2 + 1], seg[nd]));
  	lim[nd * 2] = min(lim[nd * 2], lim[nd]);
	lim[nd * 2 + 1] = min(lim[nd * 2 + 1], lim[nd]);
}

void update(int nd, int L, int R, int l, int r, int h, int t){
	// cout << nd << ' '<< L << ' ' << R<< endl;
	if (r < L || R < l) return;
	if (t == 1)	h = min(h, lim[nd]);
	if (l <= L && R <= r){
		if (t == 1) seg[nd] = max(seg[nd], h);
		else lim[nd] = min(h, lim[nd]);
		return;
	}
	clear(nd);
	update(nd * 2, L, (L + R) / 2, l, r, h, t);
	update(nd * 2 + 1, (L + R) / 2 + 1, R, l, r, h, t);
}

void end(int nd, int l, int r){
	if (l == r){
		h[l] = seg[nd];
		return;
	}
	clear(nd);
	end(nd * 2, l, (l + r) / 2);
	end(nd * 2 + 1, (l + r) / 2 + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0;i <= 4 * n;i++) lim[i] = 2e9;
	for (int i = k - 1;i >= 0;i--) update(1, 0, n - 1, left[i], right[i], height[i], op[i]); 
	end(1, 0, n - 1);
	for (int i = 0;i < n;i++) finalHeight[i] = h[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 7 ms 888 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 170 ms 8184 KB Output is correct
3 Correct 197 ms 4304 KB Output is correct
4 Correct 557 ms 11768 KB Output is correct
5 Correct 336 ms 12372 KB Output is correct
6 Correct 321 ms 12252 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 169 ms 8312 KB Output is correct
9 Correct 194 ms 4344 KB Output is correct
10 Correct 557 ms 11740 KB Output is correct
11 Correct 336 ms 12280 KB Output is correct
12 Correct 353 ms 12536 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 171 ms 8184 KB Output is correct
15 Correct 33 ms 1528 KB Output is correct
16 Correct 543 ms 12024 KB Output is correct
17 Correct 334 ms 12036 KB Output is correct
18 Correct 325 ms 12096 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 8 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 185 ms 8148 KB Output is correct
9 Correct 202 ms 4472 KB Output is correct
10 Correct 552 ms 11880 KB Output is correct
11 Correct 336 ms 12288 KB Output is correct
12 Correct 321 ms 12280 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 171 ms 8156 KB Output is correct
15 Correct 37 ms 1656 KB Output is correct
16 Correct 549 ms 12104 KB Output is correct
17 Correct 328 ms 12152 KB Output is correct
18 Correct 335 ms 12048 KB Output is correct
19 Correct 772 ms 81884 KB Output is correct
20 Correct 780 ms 79356 KB Output is correct
21 Correct 770 ms 81784 KB Output is correct
22 Correct 786 ms 79352 KB Output is correct
23 Correct 776 ms 79504 KB Output is correct
24 Correct 762 ms 79344 KB Output is correct
25 Correct 765 ms 79352 KB Output is correct
26 Correct 774 ms 81784 KB Output is correct
27 Correct 796 ms 82100 KB Output is correct
28 Correct 803 ms 79496 KB Output is correct
29 Correct 766 ms 79480 KB Output is correct
30 Correct 790 ms 79480 KB Output is correct