답안 #58093 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58093	2018-07-16T19:29:32 Z	zetapi	벽 (IOI14_wall)	C++14	100 / 100	1621 ms	65736 KB

wall

//#include "wall.h"
#include "bits/stdc++.h"
using namespace std;

#define pb  push_back
#define mp  make_pair
#define ll  long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=5e6;

struct data
{
	int Min;
	int Max;
}   Seg[MAX];

void push(int node,int CurMin,int CurMax)
{
	if(Seg[node].Max>=CurMin and Seg[node].Min<=CurMax)
	{
		CurMin=max(CurMin,Seg[node].Min);
		CurMax=min(CurMax,Seg[node].Max);
	}
	else if(Seg[node].Min>CurMax)
	    CurMin=CurMax;
	else if(Seg[node].Max<CurMin)
		CurMax=CurMin;
	Seg[node].Min=CurMin;
	Seg[node].Max=CurMax;
	return ;
}

void Update(int low,int high,int node,int qlow,int qhigh,pii delta)
{
	if(low>high or qlow>qhigh or qhigh<low or qlow>high)
		return ;
	if(low>=qlow and high<=qhigh)
	{
		if(delta.second==1)
		{
			if(Seg[node].Min>delta.first)
				return ;
			Seg[node].Min=delta.first;
			Seg[node].Max=max(Seg[node].Min,Seg[node].Max);
		}
		else
		{
			if(Seg[node].Max<delta.first)
				return ;
			Seg[node].Max=delta.first;
			Seg[node].Min=min(Seg[node].Min,Seg[node].Max);
		}
		//cout<<"updated "<<low-1<<" "<<high-1<<" previous "<<CurMin<<"  "<<CurMax<<" now its value is "<<Seg[node].Min<<" "<<Seg[node].Max<<"\n";
		//cout<<low-1<<" Updated in path "<<high-1<<" "<<Seg[node].Min<<" "<<Seg[node].Max<<"\n";
		return ;
	}
	push(2*node,Seg[node].Min,Seg[node].Max);
	push(2*node+1,Seg[node].Min,Seg[node].Max);
	Seg[node].Min=0;
	Seg[node].Max=MAX;
	int mid=(low+high)/2;
	Update(low,mid,2*node,qlow,qhigh,delta);
	Update(mid+1,high,2*node+1,qlow,qhigh,delta);
	return ;
}


int query(int low,int high,int node,int X)
{
	//cout<<low-1<<" "<<high-1<<" "<<Seg[node].Min<<" "<<Seg[node].Max<<"ha ha "<<CurMin<<" "<<CurMax<<"\n";
	if(low==high)
		return Seg[node].Min;
	push(2*node,Seg[node].Min,Seg[node].Max);
	push(2*node+1,Seg[node].Min,Seg[node].Max);
	int mid=(low+high)/2;
	if(X>=low and X<=mid)
		return query(low,mid,2*node,X);
	else
		return query(mid+1,high,2*node+1,X);
}

//void buildWall(int n=10, int k=6, vector<int> op={1,2,2,1,1,2}, vector<int> left={1,4,3,0,2,6}, vector<int> right={8,9,6,5,2,7}, vector<int> height={4,1,5,3,5,0})
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	int N=n,K=k;
	for(int A=1;A<=3*N;A++)
	{
      if(A>=MAX)
		break;
       	Seg[A].Min=0;
		Seg[A].Max=MAX;
	}
	for(int A=0;A<K;A++)
	{
		Update(1,N,1,left[A]+1,right[A]+1,mp(height[A],op[A]));
			//if(A==K-1)
			//cout<<query(1,N,1,A+1)<<" ";
		//cout<<"\n";
		//break;
	}
	//Update(1,N,1,1,N,mp(5,1));
	//Update(1,N,1,1,1,mp(0,2));
	//cout<<query(1,N,1,1)<<"\n";
	//cout<<query(1,N,1,7,0,MAX);
	for(int A=0;A<N;A++)
			finalHeight[A]=query(1,N,1,A+1);
  	return;
}

/*signed main()
{
	ios_base::sync_with_stdio(false);

	buildWall();
	return 0;
}*/

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	4 ms	612 KB	Output is correct
3	Correct	5 ms	612 KB	Output is correct
4	Correct	11 ms	1012 KB	Output is correct
5	Correct	9 ms	1012 KB	Output is correct
6	Correct	11 ms	1012 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1012 KB	Output is correct
2	Correct	197 ms	8356 KB	Output is correct
3	Correct	237 ms	8356 KB	Output is correct
4	Correct	652 ms	11332 KB	Output is correct
5	Correct	422 ms	11940 KB	Output is correct
6	Correct	483 ms	11940 KB	Output is correct

Subtask #3
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	11940 KB	Output is correct
2	Correct	4 ms	11940 KB	Output is correct
3	Correct	5 ms	11940 KB	Output is correct
4	Correct	11 ms	11940 KB	Output is correct
5	Correct	11 ms	11940 KB	Output is correct
6	Correct	10 ms	11940 KB	Output is correct
7	Correct	2 ms	11940 KB	Output is correct
8	Correct	189 ms	11940 KB	Output is correct
9	Correct	231 ms	11940 KB	Output is correct
10	Correct	710 ms	11940 KB	Output is correct
11	Correct	390 ms	11940 KB	Output is correct
12	Correct	406 ms	11940 KB	Output is correct
13	Correct	3 ms	11940 KB	Output is correct
14	Correct	254 ms	11940 KB	Output is correct
15	Correct	43 ms	11940 KB	Output is correct
16	Correct	745 ms	11940 KB	Output is correct
17	Correct	413 ms	11940 KB	Output is correct
18	Correct	442 ms	11940 KB	Output is correct

Subtask #4
39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	11940 KB	Output is correct
2	Correct	4 ms	11940 KB	Output is correct
3	Correct	5 ms	11940 KB	Output is correct
4	Correct	10 ms	11940 KB	Output is correct
5	Correct	10 ms	11940 KB	Output is correct
6	Correct	12 ms	11940 KB	Output is correct
7	Correct	3 ms	11940 KB	Output is correct
8	Correct	195 ms	11940 KB	Output is correct
9	Correct	269 ms	11940 KB	Output is correct
10	Correct	718 ms	11940 KB	Output is correct
11	Correct	451 ms	11940 KB	Output is correct
12	Correct	347 ms	12028 KB	Output is correct
13	Correct	2 ms	12028 KB	Output is correct
14	Correct	199 ms	12028 KB	Output is correct
15	Correct	47 ms	12028 KB	Output is correct
16	Correct	792 ms	12028 KB	Output is correct
17	Correct	361 ms	12028 KB	Output is correct
18	Correct	392 ms	12028 KB	Output is correct
19	Correct	1213 ms	65588 KB	Output is correct
20	Correct	1296 ms	65588 KB	Output is correct
21	Correct	1621 ms	65600 KB	Output is correct
22	Correct	1478 ms	65600 KB	Output is correct
23	Correct	1352 ms	65600 KB	Output is correct
24	Correct	1568 ms	65600 KB	Output is correct
25	Correct	1465 ms	65600 KB	Output is correct
26	Correct	1417 ms	65600 KB	Output is correct
27	Correct	1500 ms	65736 KB	Output is correct
28	Correct	1463 ms	65736 KB	Output is correct
29	Correct	1227 ms	65736 KB	Output is correct
30	Correct	1283 ms	65736 KB	Output is correct

답안 #58093

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 24.0 / 24.0

Subtask #3 29.0 / 29.0

Subtask #4 39.0 / 39.0

Subtask #1
8.0 / 8.0

Subtask #2
24.0 / 24.0

Subtask #3
29.0 / 29.0

Subtask #4
39.0 / 39.0