oj.uz

Submission #58091

# Submission time Handle Problem Language Result Execution time Memory
58091 2018-07-16T19:28:06 Z zetapi Wall (IOI14_wall) C++14
61 / 100
 838 ms 24172 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=5e5;

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 248 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 4 ms 560 KB Output is correct
4 Correct 10 ms 892 KB Output is correct
5 Correct 9 ms 892 KB Output is correct
6 Correct 10 ms 1112 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Correct 193 ms 8352 KB Output is correct
3 Correct 241 ms 8352 KB Output is correct
4 Correct 620 ms 11372 KB Output is correct
5 Correct 361 ms 11876 KB Output is correct
6 Correct 401 ms 11976 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11976 KB Output is correct
2 Correct 4 ms 11976 KB Output is correct
3 Correct 4 ms 11976 KB Output is correct
4 Correct 12 ms 11976 KB Output is correct
5 Correct 12 ms 11976 KB Output is correct
6 Correct 10 ms 11976 KB Output is correct
7 Correct 3 ms 11976 KB Output is correct
8 Correct 200 ms 11976 KB Output is correct
9 Correct 260 ms 11976 KB Output is correct
10 Correct 640 ms 11976 KB Output is correct
11 Correct 475 ms 11976 KB Output is correct
12 Correct 352 ms 11976 KB Output is correct
13 Correct 3 ms 11976 KB Output is correct
14 Correct 219 ms 11976 KB Output is correct
15 Correct 60 ms 11976 KB Output is correct
16 Correct 802 ms 11976 KB Output is correct
17 Correct 443 ms 11976 KB Output is correct
18 Correct 376 ms 11976 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11976 KB Output is correct
2 Correct 4 ms 11976 KB Output is correct
3 Correct 3 ms 11976 KB Output is correct
4 Correct 10 ms 11976 KB Output is correct
5 Correct 11 ms 11976 KB Output is correct
6 Correct 12 ms 11976 KB Output is correct
7 Correct 3 ms 11976 KB Output is correct
8 Correct 208 ms 11976 KB Output is correct
9 Correct 295 ms 11976 KB Output is correct
10 Correct 743 ms 11976 KB Output is correct
11 Correct 369 ms 11976 KB Output is correct
12 Correct 389 ms 11976 KB Output is correct
13 Correct 3 ms 11976 KB Output is correct
14 Correct 197 ms 11976 KB Output is correct
15 Correct 47 ms 11976 KB Output is correct
16 Correct 838 ms 11976 KB Output is correct
17 Correct 430 ms 11976 KB Output is correct
18 Correct 411 ms 11976 KB Output is correct
19 Runtime error 241 ms 24172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -