답안 #347123

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347123	2021-01-11T22:14:22 Z	ogibogi2004	벽 (IOI14_wall)	C++14	100 / 100	860 ms	107372 KB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6;
const int INF=2e8;
struct node
{
	int down,up;
	node()
	{
		down=INF;up=0;
	}
	node(int _down,int _up)
	{
		down=_down;
		up=_up;
	}
};
node tree[4*MAXN];
node update_d(node t,int h)
{
	t.down=min(t.down,h);
	t.up=min(t.up,t.down);
	return t;
}
node update_u(node t,int h)
{
	t.up=max(t.up,h);
	t.down=max(t.down,t.up);
	return t;
}
node update(node t1,node t2)
{
	t1.down=min(t1.down,t2.down);
	t1.up=max(t1.up,t2.up);
	t1.down=max(t1.down,t2.up);
	t1.up=min(t1.up,t2.down);
	return t1;
}
void push(int l,int r,int idx)
{
	if(tree[idx].down==INF&&tree[idx].up==0)return;
	if(l==r)return;
	tree[idx*2]=update(tree[idx*2],tree[idx]);
	tree[idx*2+1]=update(tree[idx*2+1],tree[idx]);
	tree[idx]=node(INF,0);
}
void update_d(int idx,int l,int r,int ql,int qr,int h)
{
	push(l,r,idx);
	if(l>qr)return;
	if(r<ql)return;
	if(l>=ql&&r<=qr)
	{
		tree[idx]=update_d(tree[idx],h);
		push(l,r,idx);
		return;
	}
	int mid=(l+r)/2;
	update_d(idx*2,l,mid,ql,qr,h);
	update_d(idx*2+1,mid+1,r,ql,qr,h);
}
void update_u(int idx,int l,int r,int ql,int qr,int h)
{
	push(l,r,idx);
	if(l>qr)return;
	if(r<ql)return;
	if(l>=ql&&r<=qr)
	{
		tree[idx]=update_u(tree[idx],h);
		push(l,r,idx);
		return;
	}
	int mid=(l+r)/2;
	update_u(idx*2,l,mid,ql,qr,h);
	update_u(idx*2+1,mid+1,r,ql,qr,h);
}
int ans1[4*MAXN];
void trav(int idx,int l,int r)
{
	push(l,r,idx);
	//cout<<l<<" "<<r<<" : "<<tree[idx].down<<" "<<tree[idx].up<<endl;
	if(l==r)
	{
		ans1[l]=min(tree[idx].down,tree[idx].up);
	}
	else
	{
		int mid=(l+r)/2;
		trav(idx*2,l,mid);
		trav(idx*2+1,mid+1,r);
	}
}
void trav1(int idx,int l,int r)
{
	cout<<l<<" "<<r<<" : "<<tree[idx].down<<" "<<tree[idx].up<<endl;
	//push(l,r,idx);
	if(l==r)
	{
		return;
	}
	else
	{
		int mid=(l+r)/2;
		trav1(idx*2,l,mid);
		trav1(idx*2+1,mid+1,r);
	}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	
	for(int i=0;i<k;i++)
	{
		if(op[i]==1)
		{
			update_u(1,0,n-1,left[i],right[i],height[i]);
		}
		else
		{
			update_d(1,0,n-1,left[i],right[i],height[i]);
		}
		//trav1(1,0,n-1);
		//cout<<"---------------\n";
	}
	trav(1,0,n-1);
	for(int i=0;i<n;i++)finalHeight[i]=ans1[i];
}

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	63084 KB	Output is correct
2	Correct	40 ms	63084 KB	Output is correct
3	Correct	40 ms	62956 KB	Output is correct
4	Correct	49 ms	63212 KB	Output is correct
5	Correct	44 ms	63212 KB	Output is correct
6	Correct	43 ms	63212 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	62956 KB	Output is correct
2	Correct	205 ms	70764 KB	Output is correct
3	Correct	252 ms	70252 KB	Output is correct
4	Correct	674 ms	81628 KB	Output is correct
5	Correct	355 ms	82412 KB	Output is correct
6	Correct	352 ms	81004 KB	Output is correct

Subtask #3

29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	63084 KB	Output is correct
2	Correct	40 ms	63084 KB	Output is correct
3	Correct	41 ms	62956 KB	Output is correct
4	Correct	45 ms	63212 KB	Output is correct
5	Correct	44 ms	63212 KB	Output is correct
6	Correct	44 ms	63212 KB	Output is correct
7	Correct	39 ms	62956 KB	Output is correct
8	Correct	211 ms	70764 KB	Output is correct
9	Correct	251 ms	70124 KB	Output is correct
10	Correct	648 ms	81516 KB	Output is correct
11	Correct	351 ms	82540 KB	Output is correct
12	Correct	348 ms	80876 KB	Output is correct
13	Correct	40 ms	62956 KB	Output is correct
14	Correct	210 ms	76780 KB	Output is correct
15	Correct	74 ms	64236 KB	Output is correct
16	Correct	681 ms	81664 KB	Output is correct
17	Correct	345 ms	81132 KB	Output is correct
18	Correct	347 ms	81116 KB	Output is correct

Subtask #4

39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	62956 KB	Output is correct
2	Correct	40 ms	63084 KB	Output is correct
3	Correct	40 ms	62956 KB	Output is correct
4	Correct	50 ms	63212 KB	Output is correct
5	Correct	44 ms	63212 KB	Output is correct
6	Correct	43 ms	63212 KB	Output is correct
7	Correct	40 ms	62956 KB	Output is correct
8	Correct	200 ms	70892 KB	Output is correct
9	Correct	249 ms	70124 KB	Output is correct
10	Correct	662 ms	81388 KB	Output is correct
11	Correct	351 ms	82412 KB	Output is correct
12	Correct	349 ms	80876 KB	Output is correct
13	Correct	40 ms	62956 KB	Output is correct
14	Correct	208 ms	76780 KB	Output is correct
15	Correct	74 ms	64236 KB	Output is correct
16	Correct	678 ms	81644 KB	Output is correct
17	Correct	352 ms	81132 KB	Output is correct
18	Correct	357 ms	81260 KB	Output is correct
19	Correct	802 ms	107292 KB	Output is correct
20	Correct	800 ms	104684 KB	Output is correct
21	Correct	810 ms	107372 KB	Output is correct
22	Correct	809 ms	104736 KB	Output is correct
23	Correct	833 ms	104732 KB	Output is correct
24	Correct	805 ms	104812 KB	Output is correct
25	Correct	811 ms	104704 KB	Output is correct
26	Correct	860 ms	107244 KB	Output is correct
27	Correct	840 ms	107156 KB	Output is correct
28	Correct	794 ms	104812 KB	Output is correct
29	Correct	798 ms	104812 KB	Output is correct
30	Correct	812 ms	104812 KB	Output is correct