oj.uz

답안 #126511

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126511 2019-07-08T02:37:35 Z tinjyu 벽 (IOI14_wall) C++14
100 / 100
 784 ms 101932 KB 
#include "wall.h"
#include <iostream>
using namespace std;
long long int fh[10000005],mintree[10000005],maxtree[10000005],l,r,h;
int findtree(int s,int e,int t)
{
	if(mintree[t]==maxtree[t])
	{
		for(int i=s;i<=e;i++)
		{
			fh[i]=mintree[t];
		}
		return 0;
	}
	findtree(s,(s+e)/2,t*2);
	findtree((s+e)/2+1,e,t*2+1);
}
int add(int s,int e,int t)
{
	//cout<<maxtree[t]<<" "<<mintree[t]<<" "<<s<<" "<<e<<endl;
	if(r<s || l>e)return 0;
	if(l<=s && e<=r)
	{
		if(maxtree[t]<=h)
		{
			mintree[t]=h;
			maxtree[t]=h;
			return 0;
		}
		else if(mintree[t]>=h)return 0;
	}

	if(mintree[t]==maxtree[t])
	{
		maxtree[t*2]=mintree[t*2]=maxtree[t*2+1]=mintree[t*2+1]=maxtree[t];
	}
	add(s,(s+e)/2,t*2);
	add((s+e)/2+1,e,t*2+1);
	mintree[t]=min(mintree[t*2],mintree[t*2+1]);
	maxtree[t]=max(maxtree[t*2],maxtree[t*2+1]);
}
int rem(int s,int e,int t)
{
	//cout<<maxtree[t]<<" "<<mintree[t]<<" "<<s<<" "<<e<<endl;
	if(r<s || l>e)return 0;
	if(l<=s && e<=r)
	{
		if(mintree[t]>=h)
		{
			mintree[t]=h;
			maxtree[t]=h;
			return 0;
		}
		else if(maxtree[t]<=h)return 0;
	}
	if(mintree[t]==maxtree[t])
	{
		maxtree[t*2]=mintree[t*2]=maxtree[t*2+1]=mintree[t*2+1]=maxtree[t];
	}
	rem(s,(s+e)/2,t*2);
	rem((s+e)/2+1,e,t*2+1);
	mintree[t]=min(mintree[t*2],mintree[t*2+1]);
	maxtree[t]=max(maxtree[t*2],maxtree[t*2+1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  	for(int i=0;i<k;i++)
	{
		l=left[i],r=right[i],h=height[i];
		if(op[i]==1)add(0,n-1,1);
		else rem(0,n-1,1);
		
	}
	findtree(0,n-1,1);
		for(int i=0;i<n;i++)
		{
			finalHeight[i]=fh[i];
			//cout<<fh[i]<<" ";
		}
		//cout<<endl;
 	return;
}

Compilation message

wall.cpp: In function 'int findtree(int, int, int)':
wall.cpp:17:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
wall.cpp: In function 'int add(int, int, int)':
wall.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
wall.cpp: In function 'int rem(int, int, int)':
wall.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 1144 KB Output is correct
5 Correct 7 ms 1144 KB Output is correct
6 Correct 7 ms 1144 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 172 ms 14020 KB Output is correct
3 Correct 191 ms 8696 KB Output is correct
4 Correct 566 ms 23288 KB Output is correct
5 Correct 343 ms 24312 KB Output is correct
6 Correct 332 ms 22780 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 1144 KB Output is correct
5 Correct 7 ms 1144 KB Output is correct
6 Correct 7 ms 1144 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 173 ms 13996 KB Output is correct
9 Correct 191 ms 8696 KB Output is correct
10 Correct 570 ms 23248 KB Output is correct
11 Correct 335 ms 24440 KB Output is correct
12 Correct 340 ms 22736 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 180 ms 14092 KB Output is correct
15 Correct 43 ms 2680 KB Output is correct
16 Correct 665 ms 23592 KB Output is correct
17 Correct 330 ms 23032 KB Output is correct
18 Correct 333 ms 23032 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 9 ms 1240 KB Output is correct
5 Correct 7 ms 1144 KB Output is correct
6 Correct 7 ms 1144 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 174 ms 14148 KB Output is correct
9 Correct 193 ms 8696 KB Output is correct
10 Correct 566 ms 23288 KB Output is correct
11 Correct 335 ms 24364 KB Output is correct
12 Correct 326 ms 22796 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 177 ms 13952 KB Output is correct
15 Correct 40 ms 2680 KB Output is correct
16 Correct 669 ms 23604 KB Output is correct
17 Correct 330 ms 23032 KB Output is correct
18 Correct 337 ms 23004 KB Output is correct
19 Correct 765 ms 101652 KB Output is correct
20 Correct 758 ms 99280 KB Output is correct
21 Correct 773 ms 101932 KB Output is correct
22 Correct 755 ms 99312 KB Output is correct
23 Correct 766 ms 99448 KB Output is correct
24 Correct 756 ms 99448 KB Output is correct
25 Correct 774 ms 99384 KB Output is correct
26 Correct 763 ms 101848 KB Output is correct
27 Correct 784 ms 101752 KB Output is correct
28 Correct 756 ms 99192 KB Output is correct
29 Correct 759 ms 99320 KB Output is correct
30 Correct 757 ms 99196 KB Output is correct