oj.uz

Submission #57948

# Submission time Handle Problem Language Result Execution time Memory
57948 2018-07-16T14:25:03 Z zetapi Wall (IOI14_wall) C++14
0 / 100
 220 ms 14480 KB 
#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 UpdateMin(int low,int high,int node,int qlow,int qhigh,int delta)
{
	if(low>high or qlow>qhigh or qhigh<low or qlow>high)
		return ;
	if(low>=qlow and high<=qhigh)
	{
		if(Seg[node].Min>delta)
			return ;
		Seg[node].Min=delta;
		Seg[node].Max=max(Seg[node].Max,Seg[node].Min);
		return ;
	}
	int mid=(low+high)/2;
	UpdateMin(low,mid,2*node,qlow,qhigh,delta);
	UpdateMin(mid+1,high,2*node+1,qlow,qhigh,delta);
	Seg[node].Min=max(Seg[node].Min,max(Seg[2*node].Min,Seg[2*node+1].Min));
	Seg[node].Max=min(Seg[node].Max,min(Seg[2*node].Max,Seg[2*node+1].Max));
	return ;
}

void UpdateMax(int low,int high,int node,int qlow,int qhigh,int delta)
{
	if(low>high or qlow>qhigh or qhigh<low or qlow>high)
		return ;
	if(low>=qlow and high<=qhigh)
	{
		if(Seg[node].Max<delta)
			return ;
		Seg[node].Max=delta;
		Seg[node].Min=min(Seg[node].Min,Seg[node].Max);
		return ;
	}
	int mid=(low+high)/2;
	UpdateMax(low,mid,2*node,qlow,qhigh,delta);
	UpdateMax(mid+1,high,2*node+1,qlow,qhigh,delta);
	Seg[node].Min=max(Seg[node].Min,max(Seg[2*node].Min,Seg[2*node+1].Min));
	Seg[node].Max=min(Seg[node].Max,min(Seg[2*node].Max,Seg[2*node+1].Max));
	return ;
}

int query(int low,int high,int node,int X,int CurMin,int CurMax)
{
	CurMin=max(CurMin,Seg[node].Min);
	CurMax=min(CurMax,Seg[node].Max);
	if(low==high)
		return CurMin;
	int mid=(low+high)/2;
	if(X>=low and X<=mid)
		return query(low,mid,2*node,X,CurMin,CurMax);
	else
		return query(mid+1,high,2*node+1,X,CurMin,CurMax);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	int N=n,K=k;
	for(int A=0;A<K;A++)
	{
		if(op[A]==1)
			UpdateMin(1,N,1,left[A]+1,right[A]+1,height[A]);
		else
			UpdateMax(1,N,1,left[A]+1,right[A]+1,height[A]);
	}
	for(int A=0;A<N;A++)
		finalHeight[A]=query(1,N,1,A+1,0,MAX);
  	return;
}

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

	
	return 0;
}*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 5 ms 616 KB Output is correct
3 Incorrect 3 ms 616 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 624 KB Output is correct
2 Correct 177 ms 14456 KB Output is correct
3 Incorrect 220 ms 14480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14480 KB Output is correct
2 Correct 6 ms 14480 KB Output is correct
3 Incorrect 7 ms 14480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14480 KB Output is correct
2 Correct 6 ms 14480 KB Output is correct
3 Incorrect 5 ms 14480 KB Output isn't correct
4 Halted 0 ms 0 KB -