oj.uz

Submission #282468

# Submission time Handle Problem Language Result Execution time Memory
282468 2020-08-24T12:47:50 Z Saboon Wall (IOI14_wall) C++14
100 / 100
 991 ms 100984 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;

int segmx[4*maxn], segmn[4*maxn], seglz[4*maxn];

void shift(int id){
	if (seglz[id] == -1)
		return;
	segmn[2*id+0] = segmx[2*id+0] = seglz[2*id+0] = seglz[id];
	segmn[2*id+1] = segmx[2*id+1] = seglz[2*id+1] = seglz[id];
	seglz[id] = -1;
}

int get(int id, int L, int R, int idx){
	if (L + 1 == R)
		return segmn[id];
	shift(id);
	int mid = (L + R) >> 1;
	if (idx < mid)
		return get(2*id+0, L, mid, idx);
	return get(2*id+1, mid, R, idx);
}

void add(int id, int L, int R, int l, int r, int x){
	if (r <= L or R <= l or segmn[id] >= x)
		return;
	if (l <= L and R <= r and segmx[id] <= x){
		segmn[id] = segmx[id] = seglz[id] = x;
		return;
	}
	shift(id);
	int mid = (L + R) >> 1;
	add(2*id+0, L, mid, l, r, x);
	add(2*id+1, mid, R, l, r, x);
	segmx[id] = max(segmx[2*id+0], segmx[2*id+1]);
	segmn[id] = min(segmn[2*id+0], segmn[2*id+1]);
}

void del(int id, int L, int R, int l, int r, int x){
	if (r <= L or R <= l or segmx[id] <= x)
		return;
	if (l <= L and R <= r and segmn[id] >= x){
		segmn[id] = segmx[id] = seglz[id] = x;
		return;
	}
	shift(id);
	int mid = (L + R) >> 1;
	del(2*id+0, L, mid, l, r, x);
	del(2*id+1, mid, R, l, r, x);
	segmx[id] = max(segmx[2*id+0], segmx[2*id+1]);
	segmn[id] = min(segmn[2*id+0], segmn[2*id+1]);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	memset(seglz, -1, sizeof seglz);
	for (int i = 0; i < k; i++){
		if (op[i] == 1)
			add(1, 0, n, left[i], right[i]+1, height[i]);
		else
			del(1, 0, n, left[i], right[i]+1, height[i]);
	}
	for (int i = 0; i < n; i++)
		finalHeight[i] = get(1, 0, n, i);
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31616 KB Output is correct
2 Correct 19 ms 31736 KB Output is correct
3 Correct 20 ms 31744 KB Output is correct
4 Correct 30 ms 32224 KB Output is correct
5 Correct 25 ms 32128 KB Output is correct
6 Correct 26 ms 32128 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31616 KB Output is correct
2 Correct 215 ms 45304 KB Output is correct
3 Correct 128 ms 39296 KB Output is correct
4 Correct 293 ms 51688 KB Output is correct
5 Correct 306 ms 52788 KB Output is correct
6 Correct 362 ms 51192 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31616 KB Output is correct
2 Correct 22 ms 31740 KB Output is correct
3 Correct 21 ms 31744 KB Output is correct
4 Correct 25 ms 32232 KB Output is correct
5 Correct 26 ms 32092 KB Output is correct
6 Correct 31 ms 32120 KB Output is correct
7 Correct 21 ms 31616 KB Output is correct
8 Correct 212 ms 45252 KB Output is correct
9 Correct 123 ms 39324 KB Output is correct
10 Correct 263 ms 51736 KB Output is correct
11 Correct 270 ms 52724 KB Output is correct
12 Correct 296 ms 51276 KB Output is correct
13 Correct 18 ms 31616 KB Output is correct
14 Correct 218 ms 45316 KB Output is correct
15 Correct 47 ms 33404 KB Output is correct
16 Correct 599 ms 52056 KB Output is correct
17 Correct 388 ms 51384 KB Output is correct
18 Correct 360 ms 51468 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31616 KB Output is correct
2 Correct 20 ms 31744 KB Output is correct
3 Correct 26 ms 31664 KB Output is correct
4 Correct 28 ms 32128 KB Output is correct
5 Correct 24 ms 32120 KB Output is correct
6 Correct 23 ms 32128 KB Output is correct
7 Correct 18 ms 31616 KB Output is correct
8 Correct 231 ms 45432 KB Output is correct
9 Correct 129 ms 39288 KB Output is correct
10 Correct 266 ms 51716 KB Output is correct
11 Correct 278 ms 52776 KB Output is correct
12 Correct 273 ms 51192 KB Output is correct
13 Correct 24 ms 31616 KB Output is correct
14 Correct 267 ms 45304 KB Output is correct
15 Correct 51 ms 33400 KB Output is correct
16 Correct 564 ms 51992 KB Output is correct
17 Correct 356 ms 51400 KB Output is correct
18 Correct 368 ms 51464 KB Output is correct
19 Correct 930 ms 100840 KB Output is correct
20 Correct 991 ms 98424 KB Output is correct
21 Correct 928 ms 100984 KB Output is correct
22 Correct 919 ms 98424 KB Output is correct
23 Correct 937 ms 98396 KB Output is correct
24 Correct 942 ms 98552 KB Output is correct
25 Correct 918 ms 98424 KB Output is correct
26 Correct 933 ms 100880 KB Output is correct
27 Correct 920 ms 100960 KB Output is correct
28 Correct 927 ms 98596 KB Output is correct
29 Correct 927 ms 98424 KB Output is correct
30 Correct 924 ms 98424 KB Output is correct