oj.uz

Submission #736939

# Submission time Handle Problem Language Result Execution time Memory
736939 2023-05-06T11:30:04 Z NeroZein Wall (IOI14_wall) C++17
100 / 100
 719 ms 77384 KB 
#include "wall.h"
#include "bits/stdc++.h"
using namespace std; 
#define lx (nd * 2)
#define rx (nd * 2 + 1)

const int N = 2000006;

struct node {
	int mn = 0, mx = 0; 
};

node seg[N << 2]; 
int arr[N]; 

void push (int nd) {
	for (int i = lx; i < lx + 2; ++i) {
		seg[i].mn = min(seg[i].mn, seg[nd].mn); 
		seg[i].mn = max(seg[i].mn, seg[nd].mx); 
		seg[i].mx = min(seg[i].mx, seg[nd].mn);
		seg[i].mx = max(seg[i].mx, seg[nd].mx); 
	}
}

void upd (int nd, int l, int r, int s, int e, int v, int op) {
	if (l > e || r < s) {
		return; 
	}
	if (l >= s && r <= e) {
		if (op == 1) {
			seg[nd].mx = max(seg[nd].mx, v); 
			seg[nd].mn = max(seg[nd].mn, v); 
		} else {
			seg[nd].mx = min(seg[nd].mx, v); 
			seg[nd].mn = min(seg[nd].mn, v); 
		}
		return; 
	}
	push(nd);
	seg[nd].mn = N; 
	seg[nd].mx = 0; 
	int mid = (l + r) >> 1;
	upd(lx, l, mid, s, e, v, op);
	upd(rx, mid + 1, r, s, e, v, op); 
}

inline void dive (int nd, int l, int r) {
	if (l == r) {
		arr[l] = seg[nd].mn; 
		assert(seg[nd].mn == seg[nd].mx); 
		return; 
	}
	push(nd); 
	int mid = (l + r) >> 1;
	dive(lx, l, mid);
	dive(rx, mid + 1, r); 
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < k; ++i) {
		upd(1, 0, n - 1, left[i], right[i], height[i], op[i]);
	}	
	dive(1, 0, n - 1); 
	for (int i = 0; i < n; ++i) {
		finalHeight[i] = arr[i]; 
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 784 KB Output is correct
5 Correct 4 ms 832 KB Output is correct
6 Correct 4 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 147 ms 13960 KB Output is correct
3 Correct 177 ms 8048 KB Output is correct
4 Correct 369 ms 20796 KB Output is correct
5 Correct 293 ms 21756 KB Output is correct
6 Correct 271 ms 20212 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 143 ms 13840 KB Output is correct
9 Correct 161 ms 8036 KB Output is correct
10 Correct 371 ms 20700 KB Output is correct
11 Correct 294 ms 21820 KB Output is correct
12 Correct 265 ms 20180 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 160 ms 13952 KB Output is correct
15 Correct 24 ms 1980 KB Output is correct
16 Correct 375 ms 20976 KB Output is correct
17 Correct 307 ms 20472 KB Output is correct
18 Correct 263 ms 20448 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 6 ms 836 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 138 ms 13944 KB Output is correct
9 Correct 161 ms 8044 KB Output is correct
10 Correct 378 ms 20776 KB Output is correct
11 Correct 287 ms 21784 KB Output is correct
12 Correct 290 ms 20220 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 172 ms 13936 KB Output is correct
15 Correct 24 ms 2076 KB Output is correct
16 Correct 510 ms 20976 KB Output is correct
17 Correct 331 ms 20480 KB Output is correct
18 Correct 358 ms 20504 KB Output is correct
19 Correct 653 ms 77360 KB Output is correct
20 Correct 659 ms 74792 KB Output is correct
21 Correct 711 ms 77328 KB Output is correct
22 Correct 719 ms 74868 KB Output is correct
23 Correct 667 ms 74828 KB Output is correct
24 Correct 676 ms 74860 KB Output is correct
25 Correct 665 ms 74844 KB Output is correct
26 Correct 639 ms 77384 KB Output is correct
27 Correct 618 ms 77328 KB Output is correct
28 Correct 630 ms 74884 KB Output is correct
29 Correct 632 ms 74956 KB Output is correct
30 Correct 612 ms 74852 KB Output is correct