oj.uz

Submission #298942

# Submission time Handle Problem Language Result Execution time Memory
298942 2020-09-14T10:56:32 Z aymanrs Wall (IOI14_wall) C++14
100 / 100
 1074 ms 151928 KB 
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define L(i) i*2+1
#define R(i) i*2+2
using namespace std;
typedef pair<int, int> pii;
pii *tree, *lazy;
pii update(int i, int l, int r, int a, int b, const pii& op){
	if(lazy[i].first != -1){
		tree[i].first = min(max(tree[i].first, lazy[i].first), lazy[i].second);
		tree[i].second = max(min(tree[i].second, lazy[i].second), lazy[i].first);
		if(l != r) {
			lazy[L(i)] = lazy[R(i)] = {tree[i].first, tree[i].second};
		}
		lazy[i] = {-1, -1};
	}
	if(l > b || r < a) return tree[i];
	if(a <= l && r <= b){
		if(op.first == 1){
			tree[i].first = max(tree[i].first, op.second);
			if(tree[i].first > tree[i].second){
				tree[i].second = tree[i].first;
			}
		} else {
			tree[i].second = min(tree[i].second, op.second);
			if(tree[i].first > tree[i].second){
				tree[i].first = tree[i].second;
			}
		}
		if(l != r) lazy[L(i)] = lazy[R(i)] = tree[i];
	}
	else if(l != r){
		int mid = (l+r)/2;
		pii left = update(L(i), l, mid, a, b, op), right = update(R(i), mid+1, r, a, b, op);
		tree[i] = {min(left.first, right.first), max(left.second, right.second)};
	}
	return tree[i];
}

void get(int i, int l, int r, int finalHeight[]){
	if(lazy[i].first != -1){
		tree[i].first = min(max(tree[i].first, lazy[i].first), lazy[i].second);
		tree[i].second = max(min(tree[i].second, lazy[i].second), lazy[i].first);
		if(l != r) {
			lazy[L(i)] = lazy[R(i)] = {tree[i].first, tree[i].second};
		}
		lazy[i] = {-1, -1};
	}
	if(l == r){
		finalHeight[l] = tree[i].first;
	} else {
		int mid = (l+r)/2;
		get(L(i), l, mid, finalHeight);
		get(R(i), mid+1, r, finalHeight);
	}
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
	tree = new pii[4 * n + 10];
	lazy = new pii[4 * n + 10];
	for(int i = 0;i < 4*n+10;i++) {
		lazy[i] = {-1, -1};
		tree[i] = {0, 0};
	}
	//printf("hi\n");
	for(int i = 0;i < k;i++){
		update(0, 0, n-1, left[i], right[i], {op[i], height[i]});
	}
	get(0, 0, n-1, finalHeight);
	delete[] tree;
	delete[] lazy;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 7 ms 1024 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 176 ms 8224 KB Output is correct
3 Correct 274 ms 4728 KB Output is correct
4 Correct 900 ms 24568 KB Output is correct
5 Correct 400 ms 25084 KB Output is correct
6 Correct 396 ms 23416 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 7 ms 1024 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 173 ms 8184 KB Output is correct
9 Correct 282 ms 4856 KB Output is correct
10 Correct 898 ms 24568 KB Output is correct
11 Correct 405 ms 24952 KB Output is correct
12 Correct 403 ms 23416 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 180 ms 13944 KB Output is correct
15 Correct 47 ms 2552 KB Output is correct
16 Correct 948 ms 24600 KB Output is correct
17 Correct 415 ms 23800 KB Output is correct
18 Correct 409 ms 23928 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 7 ms 1024 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 176 ms 8184 KB Output is correct
9 Correct 282 ms 4728 KB Output is correct
10 Correct 880 ms 24568 KB Output is correct
11 Correct 409 ms 25080 KB Output is correct
12 Correct 397 ms 23416 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 181 ms 13948 KB Output is correct
15 Correct 47 ms 2552 KB Output is correct
16 Correct 950 ms 24600 KB Output is correct
17 Correct 411 ms 23800 KB Output is correct
18 Correct 425 ms 23928 KB Output is correct
19 Correct 1059 ms 151800 KB Output is correct
20 Correct 1054 ms 151800 KB Output is correct
21 Correct 1070 ms 151800 KB Output is correct
22 Correct 1057 ms 151800 KB Output is correct
23 Correct 1074 ms 151804 KB Output is correct
24 Correct 1060 ms 151672 KB Output is correct
25 Correct 1059 ms 151800 KB Output is correct
26 Correct 1046 ms 151928 KB Output is correct
27 Correct 1056 ms 151800 KB Output is correct
28 Correct 1066 ms 151708 KB Output is correct
29 Correct 1039 ms 151864 KB Output is correct
30 Correct 1065 ms 151672 KB Output is correct