제출 #881611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881611		iskhakkutbilim	Wall (IOI14_wall)	C++17	0 / 100	124 ms	12840 KiB

wall

#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(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), NONE};
		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(t[v].mx <= x) return;
	if(vl == vr){
		t[v] = {min(t[v].mn, x), min(t[v].mx, x), NONE};
		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);
}

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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39