oj.uz

Submission #58093

# Submission time Handle Problem Language Result Execution time Memory
58093 2018-07-16T19:29:32 Z zetapi Wall (IOI14_wall) C++14
100 / 100
 1621 ms 65736 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++)
	{
      if(A>=MAX)
		break;
       	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 612 KB Output is correct
3 Correct 5 ms 612 KB Output is correct
4 Correct 11 ms 1012 KB Output is correct
5 Correct 9 ms 1012 KB Output is correct
6 Correct 11 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 197 ms 8356 KB Output is correct
3 Correct 237 ms 8356 KB Output is correct
4 Correct 652 ms 11332 KB Output is correct
5 Correct 422 ms 11940 KB Output is correct
6 Correct 483 ms 11940 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11940 KB Output is correct
2 Correct 4 ms 11940 KB Output is correct
3 Correct 5 ms 11940 KB Output is correct
4 Correct 11 ms 11940 KB Output is correct
5 Correct 11 ms 11940 KB Output is correct
6 Correct 10 ms 11940 KB Output is correct
7 Correct 2 ms 11940 KB Output is correct
8 Correct 189 ms 11940 KB Output is correct
9 Correct 231 ms 11940 KB Output is correct
10 Correct 710 ms 11940 KB Output is correct
11 Correct 390 ms 11940 KB Output is correct
12 Correct 406 ms 11940 KB Output is correct
13 Correct 3 ms 11940 KB Output is correct
14 Correct 254 ms 11940 KB Output is correct
15 Correct 43 ms 11940 KB Output is correct
16 Correct 745 ms 11940 KB Output is correct
17 Correct 413 ms 11940 KB Output is correct
18 Correct 442 ms 11940 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11940 KB Output is correct
2 Correct 4 ms 11940 KB Output is correct
3 Correct 5 ms 11940 KB Output is correct
4 Correct 10 ms 11940 KB Output is correct
5 Correct 10 ms 11940 KB Output is correct
6 Correct 12 ms 11940 KB Output is correct
7 Correct 3 ms 11940 KB Output is correct
8 Correct 195 ms 11940 KB Output is correct
9 Correct 269 ms 11940 KB Output is correct
10 Correct 718 ms 11940 KB Output is correct
11 Correct 451 ms 11940 KB Output is correct
12 Correct 347 ms 12028 KB Output is correct
13 Correct 2 ms 12028 KB Output is correct
14 Correct 199 ms 12028 KB Output is correct
15 Correct 47 ms 12028 KB Output is correct
16 Correct 792 ms 12028 KB Output is correct
17 Correct 361 ms 12028 KB Output is correct
18 Correct 392 ms 12028 KB Output is correct
19 Correct 1213 ms 65588 KB Output is correct
20 Correct 1296 ms 65588 KB Output is correct
21 Correct 1621 ms 65600 KB Output is correct
22 Correct 1478 ms 65600 KB Output is correct
23 Correct 1352 ms 65600 KB Output is correct
24 Correct 1568 ms 65600 KB Output is correct
25 Correct 1465 ms 65600 KB Output is correct
26 Correct 1417 ms 65600 KB Output is correct
27 Correct 1500 ms 65736 KB Output is correct
28 Correct 1463 ms 65736 KB Output is correct
29 Correct 1227 ms 65736 KB Output is correct
30 Correct 1283 ms 65736 KB Output is correct