oj.uz

답안 #1082521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1082521 2024-08-31T14:25:14 Z 4QT0R 벽 (IOI14_wall) C++17
100 / 100
 552 ms 69464 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define pii pair<int,int>

const int base=1<<21;
pii tree[2*base];

void lazy_prop(int v){
	if (v>=base)return;
	if (tree[v].first>=tree[2*v].second)tree[2*v]={tree[v].first,tree[v].first};
	else if (tree[v].second<=tree[2*v].first)tree[2*v]={tree[v].second,tree[v].second};
	else{
		tree[2*v].first=max(tree[2*v].first,tree[v].first);
		tree[2*v].second=min(tree[2*v].second,tree[v].second);
	}
	if (tree[v].first>=tree[2*v+1].second)tree[2*v+1]={tree[v].first,tree[v].first};
	else if (tree[v].second<=tree[2*v+1].first)tree[2*v+1]={tree[v].second,tree[v].second};
	else{
		tree[2*v+1].first=max(tree[2*v+1].first,tree[v].first);
		tree[2*v+1].second=min(tree[2*v+1].second,tree[v].second);
	}
}

void update(int v, int l, int p, int a, int b, pii op){
	if (a<=l && p<=b){
		if (op.first==1){
			tree[v].first=max(tree[v].first,op.second);
			tree[v].second=max(tree[v].second,tree[v].first);
		}
		else{
			tree[v].second=min(tree[v].second,op.second);
			tree[v].first=min(tree[v].second,tree[v].first);
		}
		lazy_prop(v);
		return;
	}
	else if (p<a || b<l){
		lazy_prop(v);
		return;
	}
	else{
		lazy_prop(v);
		update(2*v,l,(l+p)/2,a,b,op);
		update(2*v+1,(l+p)/2+1,p,a,b,op);
		tree[v]={min(tree[2*v].first,tree[2*v+1].first),max(tree[2*v].second,tree[2*v+1].second)};
	}
}

void finalProp(int v){
	if (v>=base)return;
	lazy_prop(v);
	finalProp(2*v);
	finalProp(2*v+1);
}

void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
	for (int i = 0; i<k; i++)update(1,0,base-1,left[i],right[i],{op[i],height[i]});
	finalProp(1);
	for (int i = 0; i<n; i++)finalHeight[i]=tree[base+i].first;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 33372 KB Output is correct
2 Correct 20 ms 33368 KB Output is correct
3 Correct 19 ms 33116 KB Output is correct
4 Correct 23 ms 33464 KB Output is correct
5 Correct 20 ms 33372 KB Output is correct
6 Correct 21 ms 33412 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 33116 KB Output is correct
2 Correct 231 ms 46660 KB Output is correct
3 Correct 164 ms 40228 KB Output is correct
4 Correct 391 ms 51284 KB Output is correct
5 Correct 264 ms 52308 KB Output is correct
6 Correct 247 ms 50772 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 33112 KB Output is correct
2 Correct 21 ms 33372 KB Output is correct
3 Correct 29 ms 33200 KB Output is correct
4 Correct 24 ms 33408 KB Output is correct
5 Correct 24 ms 33364 KB Output is correct
6 Correct 23 ms 33368 KB Output is correct
7 Correct 21 ms 33112 KB Output is correct
8 Correct 221 ms 46672 KB Output is correct
9 Correct 171 ms 40276 KB Output is correct
10 Correct 383 ms 51148 KB Output is correct
11 Correct 271 ms 52308 KB Output is correct
12 Correct 250 ms 50768 KB Output is correct
13 Correct 19 ms 33112 KB Output is correct
14 Correct 217 ms 46676 KB Output is correct
15 Correct 49 ms 34388 KB Output is correct
16 Correct 496 ms 51536 KB Output is correct
17 Correct 310 ms 50976 KB Output is correct
18 Correct 292 ms 50740 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 33116 KB Output is correct
2 Correct 19 ms 33168 KB Output is correct
3 Correct 19 ms 33116 KB Output is correct
4 Correct 22 ms 33360 KB Output is correct
5 Correct 28 ms 33388 KB Output is correct
6 Correct 23 ms 33368 KB Output is correct
7 Correct 17 ms 33116 KB Output is correct
8 Correct 215 ms 46668 KB Output is correct
9 Correct 157 ms 40276 KB Output is correct
10 Correct 403 ms 51212 KB Output is correct
11 Correct 248 ms 52304 KB Output is correct
12 Correct 254 ms 50868 KB Output is correct
13 Correct 18 ms 33368 KB Output is correct
14 Correct 222 ms 46676 KB Output is correct
15 Correct 44 ms 34384 KB Output is correct
16 Correct 480 ms 51448 KB Output is correct
17 Correct 301 ms 50756 KB Output is correct
18 Correct 286 ms 50772 KB Output is correct
19 Correct 550 ms 69456 KB Output is correct
20 Correct 540 ms 67156 KB Output is correct
21 Correct 532 ms 69460 KB Output is correct
22 Correct 536 ms 67156 KB Output is correct
23 Correct 550 ms 66988 KB Output is correct
24 Correct 552 ms 67088 KB Output is correct
25 Correct 519 ms 67152 KB Output is correct
26 Correct 524 ms 69464 KB Output is correct
27 Correct 536 ms 69456 KB Output is correct
28 Correct 526 ms 67136 KB Output is correct
29 Correct 541 ms 67156 KB Output is correct
30 Correct 533 ms 67156 KB Output is correct