oj.uz

Submission #881618

# Submission time Handle Problem Language Result Execution time Memory
881618 2023-12-01T15:44:21 Z iskhakkutbilim Wall (IOI14_wall) C++17
61 / 100
 371 ms 36352 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 = 1e5;
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 1 ms 4956 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 6 ms 5212 KB Output is correct
5 Correct 5 ms 5212 KB Output is correct
6 Correct 5 ms 5212 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 109 ms 12792 KB Output is correct
3 Correct 55 ms 8412 KB Output is correct
4 Correct 141 ms 22972 KB Output is correct
5 Correct 158 ms 24188 KB Output is correct
6 Correct 175 ms 22576 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 5040 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 5 ms 5212 KB Output is correct
5 Correct 5 ms 5212 KB Output is correct
6 Correct 5 ms 5336 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 110 ms 18772 KB Output is correct
9 Correct 56 ms 12112 KB Output is correct
10 Correct 142 ms 22992 KB Output is correct
11 Correct 157 ms 24252 KB Output is correct
12 Correct 175 ms 22564 KB Output is correct
13 Correct 1 ms 4956 KB Output is correct
14 Correct 116 ms 18772 KB Output is correct
15 Correct 22 ms 6228 KB Output is correct
16 Correct 371 ms 23536 KB Output is correct
17 Correct 256 ms 22760 KB Output is correct
18 Correct 294 ms 22652 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 5 ms 5336 KB Output is correct
5 Correct 6 ms 5212 KB Output is correct
6 Correct 6 ms 5212 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 112 ms 18764 KB Output is correct
9 Correct 68 ms 12080 KB Output is correct
10 Correct 141 ms 22956 KB Output is correct
11 Correct 153 ms 24060 KB Output is correct
12 Correct 188 ms 22664 KB Output is correct
13 Correct 1 ms 4956 KB Output is correct
14 Correct 117 ms 18668 KB Output is correct
15 Correct 23 ms 6256 KB Output is correct
16 Correct 359 ms 23380 KB Output is correct
17 Correct 258 ms 22612 KB Output is correct
18 Correct 257 ms 22612 KB Output is correct
19 Runtime error 147 ms 36352 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -