oj.uz

Submission #783829

# Submission time Handle Problem Language Result Execution time Memory
783829 2023-07-15T11:09:35 Z FatihSolak Wall (IOI14_wall) C++17
100 / 100
 885 ms 89080 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct SegTree{
	struct node{
		int maxi,mini;
		node():maxi(0),mini(0){}
	};
	vector<node> t;
	int n;
	SegTree(int sz){
		n = sz;
		t.assign(4*n,node());
	}
	void push(int v){
		t[v*2].mini = max(t[v*2].mini,t[v].mini);
		t[v*2].maxi = max(t[v*2].maxi,t[v*2].mini);
		t[v*2].maxi = min(t[v*2].maxi,t[v].maxi);
		t[v*2].mini = min(t[v*2].maxi,t[v*2].mini);
		
		t[v*2 + 1].mini = max(t[v*2 + 1].mini,t[v].mini);
		t[v*2 + 1].maxi = max(t[v*2 + 1].maxi,t[v*2 + 1].mini);
		t[v*2 + 1].maxi = min(t[v*2 + 1].maxi,t[v].maxi);
		t[v*2 + 1].mini = min(t[v*2 + 1].maxi,t[v*2 + 1].mini);
		
	}
	void upd(int v,int tl,int tr,int l,int r,int val,int op){
		if(tr < l || r < tl){
			return;
		}
		if(l <= tl && tr <= r){
			//cout << tl << ' ' << tr << endl;
			if(op == 1){
				t[v].mini = max(t[v].mini,val);
				t[v].maxi = max(t[v].maxi,t[v].mini);
			}
			else{
				t[v].maxi = min(t[v].maxi,val);
				t[v].mini = min(t[v].mini,t[v].maxi);
			}
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val,op);
		upd(v*2 + 1,tm+1,tr,l,r,val,op);
		t[v].maxi = max(t[v*2].maxi,t[v*2+1].maxi);
		t[v].mini = min(t[v*2].mini,t[v*2+1].mini);
	}
	int get(int v,int tl,int tr,int pos){
		//cout << tl << ' ' << tr << ' ' << t[v].mini << ' ' << t[v].maxi << endl;
		if(tl == tr){
			return t[v].maxi;
		}
		push(v);
		int tm = (tl + tr)/2;
		if(pos <= tm)
			return get(v*2,tl,tm,pos);
		return get(v*2+1,tm+1,tr,pos);
	}
	void upd(int l,int r,int val,int op){
		upd(1,0,n-1,l,r,val,op);
	}
	int get(int pos){
		return get(1,0,n-1,pos);
	}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree t(n);
	for(int i = 0;i<k;i++){
		t.upd(left[i],right[i],height[i],op[i]);
	}
	for(int i = 0;i<n;i++){
		finalHeight[i] = t.get(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 312 KB Output is correct
4 Correct 6 ms 824 KB Output is correct
5 Correct 5 ms 820 KB Output is correct
6 Correct 5 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 116 ms 13852 KB Output is correct
3 Correct 135 ms 7920 KB Output is correct
4 Correct 372 ms 21152 KB Output is correct
5 Correct 254 ms 21680 KB Output is correct
6 Correct 246 ms 20192 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 824 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 111 ms 13868 KB Output is correct
9 Correct 131 ms 7880 KB Output is correct
10 Correct 376 ms 21256 KB Output is correct
11 Correct 246 ms 21804 KB Output is correct
12 Correct 243 ms 20240 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 109 ms 13864 KB Output is correct
15 Correct 23 ms 1876 KB Output is correct
16 Correct 374 ms 21252 KB Output is correct
17 Correct 247 ms 20672 KB Output is correct
18 Correct 247 ms 20612 KB Output is correct

Subtask #4
39.0 / 39.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 340 KB Output is correct
4 Correct 6 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 110 ms 13884 KB Output is correct
9 Correct 138 ms 8080 KB Output is correct
10 Correct 374 ms 21144 KB Output is correct
11 Correct 255 ms 21792 KB Output is correct
12 Correct 249 ms 20232 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 111 ms 13892 KB Output is correct
15 Correct 23 ms 1864 KB Output is correct
16 Correct 416 ms 21264 KB Output is correct
17 Correct 251 ms 20676 KB Output is correct
18 Correct 298 ms 20672 KB Output is correct
19 Correct 859 ms 88904 KB Output is correct
20 Correct 885 ms 88932 KB Output is correct
21 Correct 836 ms 88964 KB Output is correct
22 Correct 834 ms 88908 KB Output is correct
23 Correct 829 ms 88988 KB Output is correct
24 Correct 843 ms 88996 KB Output is correct
25 Correct 843 ms 88956 KB Output is correct
26 Correct 843 ms 89016 KB Output is correct
27 Correct 845 ms 89048 KB Output is correct
28 Correct 842 ms 88928 KB Output is correct
29 Correct 841 ms 89080 KB Output is correct
30 Correct 846 ms 88960 KB Output is correct