oj.uz

Submission #809081

# Submission time Handle Problem Language Result Execution time Memory
809081 2023-08-05T15:51:18 Z ZeroCool Wall (IOI14_wall) C++14
100 / 100
 515 ms 77360 KB 
#include "wall.h"
#include <bits/stdc++.h>
 
const int mxn = 2000010;
const int inf = INT_MAX;
 
using namespace std;
 
struct Node{
	int mx = 0;
	int mn = 0;
};
 
int res[mxn];
Node seg[2 * (1<<21) + 20];
 
void push(int k){
	//Minimize na levoto dete
	seg[k * 2].mn = min(seg[k * 2].mn, seg[k].mn);
    seg[k * 2].mx = min(seg[k * 2].mx, seg[k].mn);
	//Maximize na levoto dete
    seg[k * 2].mn = max(seg[k * 2].mn, seg[k].mx);
    seg[k * 2].mx = max(seg[k * 2].mx, seg[k].mx);
	//Minimize na desnoto dete
    seg[k * 2 + 1].mn = min(seg[k * 2 + 1].mn, seg[k].mn);
    seg[k * 2 + 1].mx = min(seg[k * 2 + 1].mx, seg[k].mn);
	//Maximize na desnoto dete
    seg[k * 2 + 1].mn = max(seg[k * 2 + 1].mn, seg[k].mx);
    seg[k * 2 + 1].mx = max(seg[k * 2 + 1].mx, seg[k].mx);
}
 
void update(int k,int l,int r,int i,int j,int v,int t){
	if(l > j || r < i)return;
	if(i <= l && r<= j){
		if(t==1){
			//Maximize operacija
			seg[k].mn = max(seg[k].mn,v);
			seg[k].mx = max(seg[k].mx,v);
		}else{
			//Minimize operacija
			seg[k].mn = min(seg[k].mn,v);
			seg[k].mx = min(seg[k].mx,v);
		}
		return;
	}
	push(k);
	seg[k].mn = inf;
    seg[k].mx = 0;
	int mid = (l+r)/2;
	update(k*2,l,mid,i,j,v,t);
	update(k*2+1,mid+1,r,i,j,v,t);
}
 
void get(int k,int l,int r){
	if(l == r){
		res[l] = seg[k].mn;
		return;
	}
	push(k);
	int mid = (l+r)/2;
	get(k*2,l,mid);
	get(k*2+1,mid+1,r);
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 0;i<k;i++){
		update(1,0,n-1,left[i],right[i],height[i],op[i]);
	}
	get(1,0,n-1);
	for(int i = 0;i<n;i++){
		finalHeight[i] = res[i];
	}
	
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 832 KB Output is correct
6 Correct 4 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 105 ms 13912 KB Output is correct
3 Correct 121 ms 8020 KB Output is correct
4 Correct 325 ms 20708 KB Output is correct
5 Correct 213 ms 21880 KB Output is correct
6 Correct 210 ms 20260 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 105 ms 13964 KB Output is correct
9 Correct 125 ms 7976 KB Output is correct
10 Correct 323 ms 20740 KB Output is correct
11 Correct 216 ms 21844 KB Output is correct
12 Correct 209 ms 20204 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 100 ms 13884 KB Output is correct
15 Correct 20 ms 2044 KB Output is correct
16 Correct 335 ms 20972 KB Output is correct
17 Correct 222 ms 20468 KB Output is correct
18 Correct 219 ms 20452 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 768 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 101 ms 13880 KB Output is correct
9 Correct 122 ms 8052 KB Output is correct
10 Correct 330 ms 20944 KB Output is correct
11 Correct 234 ms 21836 KB Output is correct
12 Correct 219 ms 20208 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 101 ms 13876 KB Output is correct
15 Correct 19 ms 2020 KB Output is correct
16 Correct 327 ms 20972 KB Output is correct
17 Correct 224 ms 20532 KB Output is correct
18 Correct 230 ms 20436 KB Output is correct
19 Correct 504 ms 77312 KB Output is correct
20 Correct 502 ms 74956 KB Output is correct
21 Correct 506 ms 77312 KB Output is correct
22 Correct 492 ms 74804 KB Output is correct
23 Correct 495 ms 74816 KB Output is correct
24 Correct 493 ms 74872 KB Output is correct
25 Correct 497 ms 75004 KB Output is correct
26 Correct 515 ms 77260 KB Output is correct
27 Correct 499 ms 77360 KB Output is correct
28 Correct 497 ms 74752 KB Output is correct
29 Correct 494 ms 74824 KB Output is correct
30 Correct 510 ms 74784 KB Output is correct