oj.uz

Submission #597715

# Submission time Handle Problem Language Result Execution time Memory
597715 2022-07-16T15:52:15 Z 1ne Wall (IOI14_wall) C++14
100 / 100
 1303 ms 78664 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
struct dataa{
	long long minny = 1e9,maxxy = 0;
	void add(dataa v){
		minny = min(minny,v.minny);
		maxxy = max(maxxy,v.maxxy);
	}
};
long long S,T;
struct Segment_Tree{
	vector<dataa>tree;
	void init(long long n){
		tree.resize(2*n - 1);
	}
	dataa combine(dataa left,dataa right){
		dataa res;
		res.minny = max(left.minny,right.minny);
		res.maxxy = min(left.maxxy,right.maxxy);
		return res;
	}
	void push(long long node,long long left,long long right){
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		tree[node + 1].add(tree[node]);
		tree[z].add(tree[node]);
		tree[node + 1].minny = max(tree[node + 1].minny,tree[node].maxxy);
		tree[z].minny = max(tree[z].minny,tree[node].maxxy);
		tree[node + 1].maxxy = min(tree[node + 1].maxxy,tree[node].minny);
		tree[z].maxxy = min(tree[z].maxxy,tree[node].minny);
	}
	long long query(long long node,long long left,long long right,long long qleft,long long qright){
		if (qright<left|| qleft > right)return 1e9;
		if (qleft<=left && qright>=right){
			return min(tree[node].minny,tree[node].maxxy);
		}
		push(node,left,right);
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		return min(query(node + 1,left,mid,qleft,qright),query(z,mid + 1,right,qleft,qright));
	}
	void update(long long node,long long left,long long right,long long uleft,long long uright,long long h,long long type){
		if (left > uright || right < uleft) return;
		if (uleft <= left && right <=uright){
			if (type == 1){
				tree[node].minny = max(tree[node].minny,h);
				tree[node].maxxy = max(tree[node].maxxy,h);
			}
			else{
				tree[node].minny = min(tree[node].minny,h);
				tree[node].maxxy = min(tree[node].maxxy,h);
			}
			return;
		}
		push(node,left,right);
		tree[node].minny = 1e9;
		tree[node].maxxy = 0;
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		if (uleft<=mid){
			update(node + 1,left,mid,uleft,uright,h,type);
		}
		if (uright > mid){
			update(z,mid + 1,right,uleft,uright,h,type);
		}
		tree[node] = combine(tree[node + 1],tree[z]);
	}
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  Segment_Tree st;
  st.init(n);
  for (int i = 0;i<k;++i){
	st.update(0,0,n - 1,left[i],right[i],height[i],op[i]);
  }
  for (int i = 0;i<n;++i){
	finalHeight[i] = st.query(0,0,n-1,i,i);
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 7 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 123 ms 8064 KB Output is correct
3 Correct 170 ms 4256 KB Output is correct
4 Correct 460 ms 11652 KB Output is correct
5 Correct 312 ms 11648 KB Output is correct
6 Correct 299 ms 11620 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 8 ms 724 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 128 ms 8104 KB Output is correct
9 Correct 162 ms 4176 KB Output is correct
10 Correct 463 ms 11752 KB Output is correct
11 Correct 304 ms 11596 KB Output is correct
12 Correct 304 ms 11604 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 124 ms 8016 KB Output is correct
15 Correct 29 ms 1356 KB Output is correct
16 Correct 459 ms 11648 KB Output is correct
17 Correct 310 ms 11652 KB Output is correct
18 Correct 304 ms 11708 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 6 ms 724 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 117 ms 8084 KB Output is correct
9 Correct 175 ms 4084 KB Output is correct
10 Correct 461 ms 11864 KB Output is correct
11 Correct 302 ms 11644 KB Output is correct
12 Correct 302 ms 11772 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 127 ms 8028 KB Output is correct
15 Correct 29 ms 1356 KB Output is correct
16 Correct 477 ms 11616 KB Output is correct
17 Correct 302 ms 11596 KB Output is correct
18 Correct 309 ms 11700 KB Output is correct
19 Correct 1201 ms 78616 KB Output is correct
20 Correct 1189 ms 78568 KB Output is correct
21 Correct 1197 ms 78492 KB Output is correct
22 Correct 1178 ms 78664 KB Output is correct
23 Correct 1188 ms 78564 KB Output is correct
24 Correct 1217 ms 78632 KB Output is correct
25 Correct 1192 ms 78592 KB Output is correct
26 Correct 1226 ms 78564 KB Output is correct
27 Correct 1278 ms 78472 KB Output is correct
28 Correct 1303 ms 78468 KB Output is correct
29 Correct 1285 ms 78552 KB Output is correct
30 Correct 1277 ms 78528 KB Output is correct