oj.uz

Submission #881620

# Submission time Handle Problem Language Result Execution time Memory
881620 2023-12-01T15:44:53 Z iskhakkutbilim Wall (IOI14_wall) C++17
100 / 100
 720 ms 130872 KB 
#include <bits/stdc++.h>
#include <wall.h>

using namespace std;

//#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 1e9 + 7;
const int N = 2e6;
const int NONE = 1e7;
int SZN;
struct node{
	int mn, mx;
};

int lazy[N*4];
node t[N*4];


node combine(node A, node B){
	return {min(A.mn, B.mn), max(A.mx, B.mx)};
}

void push(int v, int vl, int vr){
	if(lazy[v] == NONE) return;
	t[v].mn = t[v].mx = lazy[v];
	if(vl != vr){
		
		lazy[v<<1] = lazy[v];
		lazy[v<<1|1] = lazy[v];
	}
	lazy[v] = NONE;
}

void update(int l, int r, int x, int v, int vl, int vr){
	push(v, vl, vr);
	if(l > vr or vl > r) return;
	if(l <= vl and r >= vr){
		lazy[v] = x;
		push(v, vl, vr);
		return;
	}
	int mid = (vl + vr)>>1;
	update(l, r, x, v<<1, vl, mid);
	update(l, r, x, v<<1|1, mid+1, vr);
	t[v] = combine(t[v<<1], t[v<<1|1]); 
}

void mxeq(int l, int r, int x, int v, int vl, int vr){
	push(v, vl, vr);
	if(l > vr or vl > r) return;
	
	if(t[v].mn >= x) return;
	if(t[v].mx < x){
		update(l, r, x, v, vl, vr);
		return;
	}
	if(vl == vr){
		t[v] = {max(t[v].mn, x), max(t[v].mx, x)};
		return;
	}
	int mid = (vl + vr)>>1;
	mxeq(l, r, x, v<<1, vl, mid);
	mxeq(l, r, x, v<<1|1, mid+1, vr);
	t[v] = combine(t[v<<1], t[v<<1|1]); 
}


void mneq(int l, int r, int x, int v, int vl, int vr){
	push(v, vl, vr);
	if(l > vr or vl > r) return;
	if(t[v].mx <= x) return;
	if(vl == vr){
		t[v] = {min(t[v].mn, x), min(t[v].mx, x)};
		return;
	}
	if(t[v].mn > x){
		update(l, r, x, v, vl, vr);
		return;
	}
	int mid = (vl + vr)>>1;
	mneq(l, r, x, v<<1, vl, mid);
	mneq(l, r, x, v<<1|1, mid+1, vr);
	t[v] = combine(t[v<<1], t[v<<1|1]); 
}

node get(int pos, int v, int vl, int vr){
	push(v, vl, vr);
	if(vl == vr) return t[v];
	int mid = (vl + vr)>>1;
	if(mid >= pos) return get(pos, v<<1, vl, mid);
	else return get(pos, v<<1|1, mid+1, vr);
	t[v] = combine(t[v<<1], t[v<<1|1]); 
}

void buildWall(int n, int k, int op[], int left[], int right[],
					int height[], int finalHeight[]){
	for(int i = 0;i < 4*N; i++){
		t[i] = {0, 0};
		lazy[i] = NONE;
	}					
	for(int i = 0;i < k; i++){
		int type = op[i], l = left[i], r = right[i], x = height[i];
		if(type == 1){
			mxeq(l + 1, r + 1, x, 1, 1, n);
		}else{
			mneq(l + 1, r + 1, x, 1, 1, n);
		}
	}
	for(int i = 1;i <= n; i++){
		node ans = get(i, 1, 1, n);
		if(ans.mn != ans.mx) assert(false);
		finalHeight[i-1] = ans.mn;
	}
						
}
/*

10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 5 5
2 6 7 0 






*/

/*

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	int q; cin >> q;
	int op[q], Left[q], Right[q], height[q];
	for(int i = 0;i < q; i++){
		cin >> op[i] >> Left[i] >> Right[i] >> height[i];
	}
	int F[n];
	buildWall(n, q, op, Left, Right, height, F);
	for(int i = 0;i < n; i++) cout << F[i] << ' ';
	return 0;
}
 
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 94288 KB Output is correct
2 Correct 29 ms 94288 KB Output is correct
3 Correct 26 ms 94156 KB Output is correct
4 Correct 29 ms 94296 KB Output is correct
5 Correct 32 ms 94300 KB Output is correct
6 Correct 28 ms 94404 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 94296 KB Output is correct
2 Correct 132 ms 101968 KB Output is correct
3 Correct 88 ms 97496 KB Output is correct
4 Correct 166 ms 102592 KB Output is correct
5 Correct 166 ms 103252 KB Output is correct
6 Correct 195 ms 103428 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 94300 KB Output is correct
2 Correct 24 ms 94364 KB Output is correct
3 Correct 28 ms 94288 KB Output is correct
4 Correct 31 ms 94276 KB Output is correct
5 Correct 29 ms 94292 KB Output is correct
6 Correct 27 ms 94288 KB Output is correct
7 Correct 23 ms 94156 KB Output is correct
8 Correct 135 ms 102088 KB Output is correct
9 Correct 78 ms 97700 KB Output is correct
10 Correct 160 ms 102680 KB Output is correct
11 Correct 166 ms 103140 KB Output is correct
12 Correct 188 ms 103252 KB Output is correct
13 Correct 22 ms 94296 KB Output is correct
14 Correct 134 ms 101968 KB Output is correct
15 Correct 45 ms 94836 KB Output is correct
16 Correct 388 ms 103052 KB Output is correct
17 Correct 271 ms 102992 KB Output is correct
18 Correct 278 ms 102992 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 94300 KB Output is correct
2 Correct 24 ms 94400 KB Output is correct
3 Correct 24 ms 94300 KB Output is correct
4 Correct 32 ms 94512 KB Output is correct
5 Correct 27 ms 94300 KB Output is correct
6 Correct 28 ms 94292 KB Output is correct
7 Correct 24 ms 94300 KB Output is correct
8 Correct 131 ms 101972 KB Output is correct
9 Correct 76 ms 97612 KB Output is correct
10 Correct 159 ms 102708 KB Output is correct
11 Correct 164 ms 103220 KB Output is correct
12 Correct 188 ms 103248 KB Output is correct
13 Correct 22 ms 94300 KB Output is correct
14 Correct 159 ms 102080 KB Output is correct
15 Correct 43 ms 94864 KB Output is correct
16 Correct 414 ms 102972 KB Output is correct
17 Correct 281 ms 102992 KB Output is correct
18 Correct 272 ms 102968 KB Output is correct
19 Correct 716 ms 120388 KB Output is correct
20 Correct 688 ms 127996 KB Output is correct
21 Correct 699 ms 130560 KB Output is correct
22 Correct 689 ms 128100 KB Output is correct
23 Correct 689 ms 128236 KB Output is correct
24 Correct 720 ms 128236 KB Output is correct
25 Correct 682 ms 128084 KB Output is correct
26 Correct 715 ms 130268 KB Output is correct
27 Correct 700 ms 130872 KB Output is correct
28 Correct 686 ms 127992 KB Output is correct
29 Correct 684 ms 128244 KB Output is correct
30 Correct 687 ms 128112 KB Output is correct