oj.uz

답안 #291933

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291933 2020-09-06T03:44:00 Z TMJN 벽 (IOI14_wall) C++17
100 / 100
 816 ms 69628 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

pair<int,int>tree[1<<22];

pair<int,int>merge(pair<int,int>x,pair<int,int>y){
	pair<int,int>p={min(x.first,y.first),max(x.second,y.second)};
	if(p.first<p.second){
		if(x.second>y.first){
			p.second=p.first;
		}
		else{
			p.first=p.second;
		}
	}
	return p;
}

void update(int k,int l,int r,int p,int q,pair<int,int>val){
	if(q<l||r<p)return;
	else if(p<=l&&r<=q){
		tree[k]=merge(tree[k],val);
	}
	else{
		tree[k+k]=merge(tree[k+k],tree[k]);
		tree[k+k+1]=merge(tree[k+k+1],tree[k]);
		tree[k]={0xE869120,0};
		update(k+k,l,(l+r)/2,p,q,val);
		update(k+k+1,(l+r)/2+1,r,p,q,val);
	}
}

int calc(int x){
	pair<int,int>a={0,0};
	x+=(1<<21);
	while(x){
		a=merge(a,tree[x]);
		x/=2;
	}
	return a.first;
}


void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<(1<<22);i++){
		tree[i]={0,0};
	}
	for(int i=0;i<K;i++){
		if(op[i]==1){
			update(1,0,(1<<21)-1,left[i],right[i],pair<int,int>{0xE869120,height[i]});
		}
		else{
			update(1,0,(1<<21)-1,left[i],right[i],pair<int,int>{height[i],0});
		}
	}
	for(int i=0;i<N;i++){
		finalHeight[i]=calc(i);
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 33152 KB Output is correct
2 Correct 23 ms 33272 KB Output is correct
3 Correct 21 ms 33152 KB Output is correct
4 Correct 27 ms 33408 KB Output is correct
5 Correct 25 ms 33408 KB Output is correct
6 Correct 25 ms 33400 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 33152 KB Output is correct
2 Correct 336 ms 46840 KB Output is correct
3 Correct 214 ms 40312 KB Output is correct
4 Correct 559 ms 51192 KB Output is correct
5 Correct 377 ms 52216 KB Output is correct
6 Correct 357 ms 50680 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 33280 KB Output is correct
2 Correct 22 ms 33280 KB Output is correct
3 Correct 21 ms 33152 KB Output is correct
4 Correct 26 ms 33408 KB Output is correct
5 Correct 25 ms 33408 KB Output is correct
6 Correct 24 ms 33400 KB Output is correct
7 Correct 19 ms 33144 KB Output is correct
8 Correct 346 ms 46840 KB Output is correct
9 Correct 216 ms 40444 KB Output is correct
10 Correct 550 ms 51320 KB Output is correct
11 Correct 360 ms 52220 KB Output is correct
12 Correct 351 ms 50680 KB Output is correct
13 Correct 19 ms 33152 KB Output is correct
14 Correct 340 ms 46840 KB Output is correct
15 Correct 57 ms 34296 KB Output is correct
16 Correct 657 ms 51448 KB Output is correct
17 Correct 368 ms 50936 KB Output is correct
18 Correct 362 ms 50936 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 33152 KB Output is correct
2 Correct 24 ms 33280 KB Output is correct
3 Correct 24 ms 33272 KB Output is correct
4 Correct 29 ms 33408 KB Output is correct
5 Correct 27 ms 33408 KB Output is correct
6 Correct 27 ms 33404 KB Output is correct
7 Correct 21 ms 33152 KB Output is correct
8 Correct 332 ms 46840 KB Output is correct
9 Correct 225 ms 40472 KB Output is correct
10 Correct 547 ms 51192 KB Output is correct
11 Correct 369 ms 52344 KB Output is correct
12 Correct 363 ms 50808 KB Output is correct
13 Correct 21 ms 33152 KB Output is correct
14 Correct 340 ms 46748 KB Output is correct
15 Correct 59 ms 34296 KB Output is correct
16 Correct 656 ms 51576 KB Output is correct
17 Correct 373 ms 50936 KB Output is correct
18 Correct 367 ms 50936 KB Output is correct
19 Correct 808 ms 69624 KB Output is correct
20 Correct 799 ms 67288 KB Output is correct
21 Correct 799 ms 69628 KB Output is correct
22 Correct 804 ms 67192 KB Output is correct
23 Correct 801 ms 67196 KB Output is correct
24 Correct 803 ms 67100 KB Output is correct
25 Correct 803 ms 67192 KB Output is correct
26 Correct 801 ms 69624 KB Output is correct
27 Correct 816 ms 69624 KB Output is correct
28 Correct 795 ms 67064 KB Output is correct
29 Correct 805 ms 67108 KB Output is correct
30 Correct 802 ms 67072 KB Output is correct