oj.uz

Submission #347123

# Submission time Handle Problem Language Result Execution time Memory
347123 2021-01-11T22:14:22 Z ogibogi2004 Wall (IOI14_wall) C++14
100 / 100
 860 ms 107372 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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