oj.uz

Submission #58092

# Submission time Handle Problem Language Result Execution time Memory
58092 2018-07-16T19:28:47 Z zetapi Wall (IOI14_wall) C++14
61 / 100
 823 ms 94756 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 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++)
	{
		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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 616 KB Output is correct
3 Correct 4 ms 616 KB Output is correct
4 Correct 12 ms 924 KB Output is correct
5 Correct 10 ms 1012 KB Output is correct
6 Correct 13 ms 1012 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1012 KB Output is correct
2 Correct 206 ms 8416 KB Output is correct
3 Correct 228 ms 8416 KB Output is correct
4 Correct 623 ms 11420 KB Output is correct
5 Correct 452 ms 12044 KB Output is correct
6 Correct 500 ms 12044 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12044 KB Output is correct
2 Correct 4 ms 12044 KB Output is correct
3 Correct 4 ms 12044 KB Output is correct
4 Correct 12 ms 12044 KB Output is correct
5 Correct 13 ms 12044 KB Output is correct
6 Correct 10 ms 12044 KB Output is correct
7 Correct 3 ms 12044 KB Output is correct
8 Correct 215 ms 12044 KB Output is correct
9 Correct 251 ms 12044 KB Output is correct
10 Correct 793 ms 12044 KB Output is correct
11 Correct 347 ms 12044 KB Output is correct
12 Correct 341 ms 12044 KB Output is correct
13 Correct 5 ms 12044 KB Output is correct
14 Correct 180 ms 12044 KB Output is correct
15 Correct 41 ms 12044 KB Output is correct
16 Correct 823 ms 12044 KB Output is correct
17 Correct 351 ms 12044 KB Output is correct
18 Correct 379 ms 12044 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12044 KB Output is correct
2 Correct 4 ms 12044 KB Output is correct
3 Correct 3 ms 12044 KB Output is correct
4 Correct 11 ms 12044 KB Output is correct
5 Correct 10 ms 12044 KB Output is correct
6 Correct 10 ms 12044 KB Output is correct
7 Correct 3 ms 12044 KB Output is correct
8 Correct 202 ms 12044 KB Output is correct
9 Correct 239 ms 12044 KB Output is correct
10 Correct 736 ms 12044 KB Output is correct
11 Correct 427 ms 12044 KB Output is correct
12 Correct 456 ms 12044 KB Output is correct
13 Correct 3 ms 12044 KB Output is correct
14 Correct 220 ms 12044 KB Output is correct
15 Correct 42 ms 12044 KB Output is correct
16 Correct 807 ms 12044 KB Output is correct
17 Correct 394 ms 12044 KB Output is correct
18 Correct 412 ms 12044 KB Output is correct
19 Runtime error 364 ms 94756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -