oj.uz

Submission #122829

# Submission time Handle Problem Language Result Execution time Memory
122829 2019-06-29T10:47:57 Z turbat Wall (IOI14_wall) C++14
61 / 100
 557 ms 32248 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define N 500005

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 4 ms 504 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 760 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 169 ms 8332 KB Output is correct
3 Correct 195 ms 4316 KB Output is correct
4 Correct 543 ms 11768 KB Output is correct
5 Correct 336 ms 12280 KB Output is correct
6 Correct 325 ms 12256 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 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 7 ms 764 KB Output is correct
5 Correct 7 ms 932 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 8156 KB Output is correct
9 Correct 196 ms 4344 KB Output is correct
10 Correct 554 ms 11720 KB Output is correct
11 Correct 392 ms 12316 KB Output is correct
12 Correct 337 ms 12280 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 190 ms 8312 KB Output is correct
15 Correct 33 ms 1528 KB Output is correct
16 Correct 557 ms 12024 KB Output is correct
17 Correct 354 ms 12124 KB Output is correct
18 Correct 326 ms 12024 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 420 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 7 ms 860 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 8116 KB Output is correct
9 Correct 195 ms 4404 KB Output is correct
10 Correct 546 ms 11816 KB Output is correct
11 Correct 340 ms 12280 KB Output is correct
12 Correct 323 ms 12280 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 172 ms 8184 KB Output is correct
15 Correct 33 ms 1560 KB Output is correct
16 Correct 550 ms 12096 KB Output is correct
17 Correct 329 ms 12024 KB Output is correct
18 Correct 326 ms 12152 KB Output is correct
19 Runtime error 228 ms 32248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -