oj.uz

Submission #969022

# Submission time Handle Problem Language Result Execution time Memory
969022 2024-04-24T11:39:46 Z elotelo966 Wall (IOI14_wall) C++17
100 / 100
 438 ms 107308 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mid (start+end)/2

pair<int,int> lazy[8000000];
int fin[2000000];


inline int push(int node,int cur){
	cur=max(cur,lazy[node].fi);
	cur=min(cur,lazy[node].se);
	return cur;
}

inline void update(int node,int start,int end,int l,int r,int val,int sem){
	if(start>end || start>r || end<l)return ;
	val=push(node,val);
	if(start>=l && end<=r){
		//cout<<node<<" "<<start<<" "<<end<<" "<<l<<" "<<r<<" "<<val<<" "<<sem<<endl;
		if(sem==1)lazy[node].fi=val;
		else lazy[node].se=val;
		//cout<<lazy[node].fi<<" "<<lazy[node].se<<" "<<endl<<endl;
		return ;
	}
	update(node*2,start,mid,l,r,val,sem),update(node*2+1,mid+1,end,l,r,val,sem);
}

inline void finish(int node,int start,int end,int cur){
	if(start>end)return ;
	cur=push(node,cur);
	if(start==end){
		fin[start]=cur;
		return ;
	}
	finish(node*2,start,mid,cur),finish(node*2+1,mid+1,end,cur);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<=4*n;i++){
		lazy[i]={-INT_MAX,INT_MAX};
	}
	for(int i=k-1;i>=0;i--){
		if(op[i]==1){
			update(1,0,n-1,left[i],right[i],height[i],1);
		}
		else{
			update(1,0,n-1,left[i],right[i],height[i],-1);
		}
	}
	
	finish(1,0,n-1,0);
	
	for(int i=0;i<n;i++){
		finalHeight[i]=fin[i];
		if(fin[i]==-INT_MAX)finalHeight[i]=0;
	}
	
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 106 ms 15956 KB Output is correct
3 Correct 98 ms 10300 KB Output is correct
4 Correct 263 ms 26620 KB Output is correct
5 Correct 178 ms 27728 KB Output is correct
6 Correct 164 ms 26192 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 104 ms 15988 KB Output is correct
9 Correct 99 ms 11604 KB Output is correct
10 Correct 260 ms 26704 KB Output is correct
11 Correct 181 ms 27644 KB Output is correct
12 Correct 163 ms 26192 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 106 ms 15988 KB Output is correct
15 Correct 16 ms 3672 KB Output is correct
16 Correct 277 ms 27104 KB Output is correct
17 Correct 171 ms 26448 KB Output is correct
18 Correct 169 ms 26448 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2692 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 101 ms 15956 KB Output is correct
9 Correct 108 ms 11668 KB Output is correct
10 Correct 259 ms 26676 KB Output is correct
11 Correct 173 ms 27648 KB Output is correct
12 Correct 166 ms 26268 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 125 ms 15956 KB Output is correct
15 Correct 20 ms 3676 KB Output is correct
16 Correct 277 ms 26980 KB Output is correct
17 Correct 184 ms 26448 KB Output is correct
18 Correct 209 ms 26268 KB Output is correct
19 Correct 435 ms 107120 KB Output is correct
20 Correct 396 ms 104732 KB Output is correct
21 Correct 413 ms 107308 KB Output is correct
22 Correct 403 ms 104572 KB Output is correct
23 Correct 395 ms 104540 KB Output is correct
24 Correct 397 ms 104576 KB Output is correct
25 Correct 412 ms 104528 KB Output is correct
26 Correct 438 ms 107092 KB Output is correct
27 Correct 411 ms 107084 KB Output is correct
28 Correct 436 ms 104672 KB Output is correct
29 Correct 404 ms 104660 KB Output is correct
30 Correct 407 ms 104608 KB Output is correct