oj.uz

답안 #332108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332108 2020-12-01T13:30:51 Z zggf 벽 (IOI14_wall) C++14
100 / 100
 845 ms 69612 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

int pot(int x){
	int tmp = 1;
	while(x){
		x/=2;
		tmp*=2;
	}
	return tmp;
}

vector<pair<int, int>> tree;
int treeSize;

void push(int x){
	if(x>=treeSize) return;
	int pt  = x*2;
	tree[pt].first = max(tree[pt].first, tree[x].first);	
	tree[pt].first = min(tree[pt].first, tree[x].second);	
	tree[pt].second = min(tree[pt].second, tree[x].second);
	tree[pt].second = max(tree[pt].second, tree[x].first);
	pt=x*2+1;
	tree[pt].first = max(tree[pt].first, tree[x].first);	
	tree[pt].first = min(tree[pt].first, tree[x].second);	
	tree[pt].second = min(tree[pt].second, tree[x].second);
	tree[pt].second = max(tree[pt].second, tree[x].first);
	
	tree[x] = {0, 1e9};
}

void update(int a, int b, int v, int t, int q = 0, int r = treeSize-1, int pt = 1){
	if(a==q&&b==r){
		if(t){
			tree[pt].first = max(tree[pt].first, v);	
			tree[pt].second = max(tree[pt].first, tree[pt].second);
		}	
		if(!t){
			tree[pt].second = min(v, tree[pt].second);
			tree[pt].first = min(tree[pt].first, tree[pt].second);	
		}	
		return;
	}	
	
	push(pt);
	int mid = (q+r)/2;
	
	if(a<=mid) update(a, min(b, mid), v, t, q, mid, pt*2);
	if(b>mid) update(max(a, mid+1), b, v, t, mid+1, r, pt*2+1);
}

void ultraPush(int pt){
	if(pt>=treeSize) return;
	
	push(pt);
	ultraPush(pt*2);
	ultraPush(pt*2+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	treeSize = pot(n);	
	tree.resize(treeSize*2+1, {0, 1e9});
	for(int i = 0; i < k; i++){
		update(left[i], right[i], height[i], op[i]==1);	
	}
	ultraPush(1);
	for(int i = 0; i < n; i++){
		finalHeight[i] = tree[i+treeSize].first;	
	}
	return;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 178 ms 14012 KB Output is correct
3 Correct 200 ms 8044 KB Output is correct
4 Correct 564 ms 20460 KB Output is correct
5 Correct 335 ms 21484 KB Output is correct
6 Correct 335 ms 20096 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 174 ms 13932 KB Output is correct
9 Correct 203 ms 8044 KB Output is correct
10 Correct 547 ms 20460 KB Output is correct
11 Correct 334 ms 21484 KB Output is correct
12 Correct 352 ms 19948 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 177 ms 13932 KB Output is correct
15 Correct 33 ms 2028 KB Output is correct
16 Correct 537 ms 20844 KB Output is correct
17 Correct 339 ms 20204 KB Output is correct
18 Correct 332 ms 20332 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 172 ms 13932 KB Output is correct
9 Correct 193 ms 8044 KB Output is correct
10 Correct 540 ms 20460 KB Output is correct
11 Correct 336 ms 21484 KB Output is correct
12 Correct 333 ms 19948 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 174 ms 13932 KB Output is correct
15 Correct 32 ms 2028 KB Output is correct
16 Correct 549 ms 20760 KB Output is correct
17 Correct 341 ms 20076 KB Output is correct
18 Correct 356 ms 20292 KB Output is correct
19 Correct 828 ms 69612 KB Output is correct
20 Correct 819 ms 67200 KB Output is correct
21 Correct 829 ms 69608 KB Output is correct
22 Correct 819 ms 67308 KB Output is correct
23 Correct 814 ms 67180 KB Output is correct
24 Correct 817 ms 67280 KB Output is correct
25 Correct 814 ms 67180 KB Output is correct
26 Correct 823 ms 69560 KB Output is correct
27 Correct 845 ms 69560 KB Output is correct
28 Correct 823 ms 67184 KB Output is correct
29 Correct 816 ms 67188 KB Output is correct
30 Correct 839 ms 67000 KB Output is correct