Submission #232844

#	Time	Username	Problem	Language	Result	Execution time	Memory
232844		kshitij_sodani	Wall (IOI14_wall)	C++17	100 / 100	972 ms	138616 KiB

wall

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb puodsh_back
#define a first
#define b second
#include "wall.h"
int tree[8000000];
int lazy[8000000][2];
int ans[2000000];
int k;

void update(int no,int l,int r,int aa,int bb,int val,int tt){
		if(tree[no]<lazy[no][0]){
			tree[no]=lazy[no][0];
		}
		else if(tree[no]>lazy[no][1]){
			tree[no]=lazy[no][1];
		}
	if(l<r){
		if(lazy[no][0]>lazy[no*2+1][1]){
			lazy[no*2+1][0]=lazy[no][0];
			lazy[no*2+1][1]=lazy[no][0];
		}
		else if(lazy[no][1]<lazy[no*2+1][0]){
			lazy[no*2+1][0]=lazy[no][1];
			lazy[no*2+1][1]=lazy[no][1];
		}
		else{
			lazy[no*2+1][0]=max(lazy[no][0],lazy[no*2+1][0]);
			lazy[no*2+1][1]=min(lazy[no][1],lazy[no*2+1][1]);
		}
		if(lazy[no][0]>lazy[no*2+2][1]){
			lazy[no*2+2][0]=lazy[no][0];
			lazy[no*2+2][1]=lazy[no][0];
		}
		else if(lazy[no][1]<lazy[no*2+2][0]){
			lazy[no*2+2][0]=lazy[no][1];
			lazy[no*2+2][1]=lazy[no][1];
		}
		else{
			lazy[no*2+2][0]=max(lazy[no][0],lazy[no*2+2][0]);
			lazy[no*2+2][1]=min(lazy[no][1],lazy[no*2+2][1]);
		}
		
	}
	lazy[no][0]=0;
	lazy[no][1]=100001;
	if(r<aa or l>bb or l>r){
		return ;
	}
	if(aa<=l and r<=bb){
		if(tt==0){
			tree[no]=min(tree[no],val);
		}
		else{
			tree[no]=max(tree[no],val);
		}
	//	cout<<l<<","<<r<<","<<val<<","<<tree[no]<<"<"<<no<<endl;
		if(l<r){
			if(tt==0){
				lazy[no*2+1][0]=min(lazy[no*2+1][0],val);
				lazy[no*2+1][1]=min(lazy[no*2+1][1],val);
			}
			else{
				lazy[no*2+1][0]=max(lazy[no*2+1][0],val);
				lazy[no*2+1][1]=max(lazy[no*2+1][1],val);
			}
			if(tt==0){
				lazy[no*2+2][0]=min(lazy[no*2+2][0],val);
				lazy[no*2+2][1]=min(lazy[no*2+2][1],val);
			}
			else{
				lazy[no*2+2][0]=max(lazy[no*2+2][0],val);
				lazy[no*2+2][1]=max(lazy[no*2+2][1],val);
			}
		}
	}
	else{
		int mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,val,tt);
		update(no*2+2,mid+1,r,aa,bb,val,tt);
	}
}
int fin(int no,int l,int r){
	if(tree[no]<lazy[no][0]){
		tree[no]=lazy[no][0];
	}
	else if(tree[no]>lazy[no][1]){
		tree[no]=lazy[no][1];
	}
	if(l<r){

		if(lazy[no][0]>lazy[no*2+1][1]){
			lazy[no*2+1][0]=lazy[no][0];
			lazy[no*2+1][1]=lazy[no][0];
		}
		else if(lazy[no][1]<lazy[no*2+1][0]){
			lazy[no*2+1][0]=lazy[no][1];
			lazy[no*2+1][1]=lazy[no][1];
		}
		else{
			lazy[no*2+1][0]=max(lazy[no][0],lazy[no*2+1][0]);
			lazy[no*2+1][1]=min(lazy[no][1],lazy[no*2+1][1]);
		}
		if(lazy[no][0]>lazy[no*2+2][1]){
			lazy[no*2+2][0]=lazy[no][0];
			lazy[no*2+2][1]=lazy[no][0];
		}
		else if(lazy[no][1]<lazy[no*2+2][0]){
			lazy[no*2+2][0]=lazy[no][1];
			lazy[no*2+2][1]=lazy[no][1];
		}
		else{
			lazy[no*2+2][0]=max(lazy[no][0],lazy[no*2+2][0]);
			lazy[no*2+2][1]=min(lazy[no][1],lazy[no*2+2][1]);
		}
		
	}
	lazy[no][0]=0;
	lazy[no][1]=100001;
	if(l==r){
		ans[l]=tree[no];
	}
	if(l<r){
		int mid=(l+r)/2;
		fin(no*2+1,l,mid);
		fin(no*2+2,mid+1,r);
	}
}
void buildWall(int n, int kk, int op[], int left[], int right[],int height[], int finalHeight[]){
	for(int i=0;i<8000000;i++){
		lazy[i][0]=0;
		lazy[i][1]=100001;
		tree[i]=0;
	}
	k=kk;
	for(int i=0;i<kk;i++){
		if(op[i]==1){
			update(0,0,n-1,left[i],right[i],height[i],1);
		}
		else{
			update(0,0,n-1,left[i],right[i],height[i],0);
		}
	}
//	cout<<tree[16]<<endl;
	fin(0,0,n-1);
	for(int i=0;i<n;i++){
		finalHeight[i]=ans[i];
//		cout<<ans[i]<<" ";
	}
//	return finalHeight;

//	cout<<endl;
}

/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int op[6];
	int left[6];int right[6];int height[6];
	op[0]=1;
	left[0]=1;
	right[0]=8;
	height[0]=4;

	op[1]=2;
	left[1]=4;
	right[1]=9;
	height[1]=1;

	op[2]=2;
	left[2]=3;
	right[2]=6;
	height[2]=5;

	op[3]=1;
	left[3]=0;
	right[3]=5;
	height[3]=3;

	op[4]=1;
	left[4]=2;
	right[4]=2;
	height[4]=5;

	op[5]=2;
	left[5]=6;
	right[5]=7;
	height[5]=0;
	int ar[10];
	buildWall(10,6,op,left,right,height,ar);
	for(int i=0;i<10;i++){
		cout<<ar[i]<<" ";
	}
	cout<<endl;








	return 0;
}*/

Compilation message (stderr)

wall.cpp: In function 'int fin(int, int, int)':
wall.cpp:132:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39