oj.uz

Submission #881590

# Submission time Handle Problem Language Result Execution time Memory
881590 2023-12-01T14:57:01 Z iskhakkutbilim Wall (IOI14_wall) C++17
0 / 100
 115 ms 12856 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, lazy;
};

node t[N*4];
void push(int v, int vl, int vr){
	if(t[v].lazy == NONE) return;
	t[v].mn = t[v].mx = t[v].lazy;
	if(vl != vr){
		t[v<<1].lazy = t[v].lazy;
		t[v<<1|1].lazy = t[v].lazy;
	}
	t[v].lazy = 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){
		t[v].lazy = 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);
}

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(l <= vl and r >= vr){
		if(t[v].mn >= x) return;
		if(vl == vr){
			t[v] = {max(t[v].mn, x), max(t[v].mn, x), NONE};
			return;
		}
		if(t[v].mx <= x){
			update(vl, vr, x, 1, 0, SZN-1);
			return;
		}
	}
	int mid = (vl + vr)>>1;
	mxeq(l, r, x, v<<1, vl, mid);
	mxeq(l, r, x, v<<1|1, mid+1, vr);
}


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(l <= vl and r >= vr){
		if(t[v].mx <= x) return;
		if(vl == vr){
			t[v] = {min(t[v].mn, x), min(t[v].mn, x), NONE};
			return;
		}
		if(t[v].mn >= x){
			update(vl, vr, x, 1, 0, SZN - 1);
			return;
		}
		
	}
	int mid = (vl + vr)>>1;
	mneq(l, r, x, v<<1, vl, mid);
	mneq(l, r, x, v<<1|1, mid+1, vr);
}

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);
}

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, 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, r, x, 1, 0, n-1);
		}else{
			mneq(l, r, x, 1, 0, n-1);
		}
	}
	for(int i = 0;i < n; i++){
		node ans = get(i,  1, 0, n-1);
		if(ans.mn != ans.mx) assert(false);
		finalHeight[i] = 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Incorrect 2 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 100 ms 12856 KB Output is correct
3 Incorrect 115 ms 8532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Incorrect 3 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 Incorrect 2 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -