oj.uz

Submission #232844

# Submission time Handle Problem Language Result Execution time Memory
232844 2020-05-18T10:53:05 Z kshitij_sodani Wall (IOI14_wall) C++17
100 / 100
 972 ms 138616 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94200 KB Output is correct
2 Correct 59 ms 94328 KB Output is correct
3 Correct 58 ms 94456 KB Output is correct
4 Correct 64 ms 94584 KB Output is correct
5 Correct 62 ms 94584 KB Output is correct
6 Correct 62 ms 94588 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 94328 KB Output is correct
2 Correct 244 ms 108152 KB Output is correct
3 Correct 275 ms 101496 KB Output is correct
4 Correct 683 ms 112736 KB Output is correct
5 Correct 467 ms 113784 KB Output is correct
6 Correct 444 ms 112248 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94200 KB Output is correct
2 Correct 57 ms 94456 KB Output is correct
3 Correct 59 ms 94456 KB Output is correct
4 Correct 63 ms 94584 KB Output is correct
5 Correct 61 ms 94584 KB Output is correct
6 Correct 64 ms 94584 KB Output is correct
7 Correct 58 ms 94200 KB Output is correct
8 Correct 241 ms 108136 KB Output is correct
9 Correct 279 ms 101496 KB Output is correct
10 Correct 690 ms 112688 KB Output is correct
11 Correct 463 ms 113784 KB Output is correct
12 Correct 448 ms 112248 KB Output is correct
13 Correct 56 ms 94200 KB Output is correct
14 Correct 249 ms 107896 KB Output is correct
15 Correct 96 ms 95480 KB Output is correct
16 Correct 861 ms 113016 KB Output is correct
17 Correct 462 ms 112336 KB Output is correct
18 Correct 451 ms 112376 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94200 KB Output is correct
2 Correct 55 ms 94328 KB Output is correct
3 Correct 57 ms 94328 KB Output is correct
4 Correct 62 ms 94584 KB Output is correct
5 Correct 60 ms 94584 KB Output is correct
6 Correct 59 ms 94584 KB Output is correct
7 Correct 55 ms 94200 KB Output is correct
8 Correct 231 ms 107928 KB Output is correct
9 Correct 273 ms 101496 KB Output is correct
10 Correct 695 ms 112764 KB Output is correct
11 Correct 457 ms 113784 KB Output is correct
12 Correct 441 ms 112248 KB Output is correct
13 Correct 53 ms 94200 KB Output is correct
14 Correct 239 ms 107984 KB Output is correct
15 Correct 96 ms 95480 KB Output is correct
16 Correct 853 ms 113020 KB Output is correct
17 Correct 461 ms 112376 KB Output is correct
18 Correct 470 ms 112440 KB Output is correct
19 Correct 964 ms 138480 KB Output is correct
20 Correct 938 ms 136056 KB Output is correct
21 Correct 950 ms 138616 KB Output is correct
22 Correct 965 ms 136184 KB Output is correct
23 Correct 963 ms 136012 KB Output is correct
24 Correct 951 ms 135960 KB Output is correct
25 Correct 959 ms 136012 KB Output is correct
26 Correct 946 ms 138440 KB Output is correct
27 Correct 972 ms 138488 KB Output is correct
28 Correct 962 ms 135928 KB Output is correct
29 Correct 959 ms 135932 KB Output is correct
30 Correct 934 ms 136056 KB Output is correct