제출 #881620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881620		iskhakkutbilim	Wall (IOI14_wall)	C++17	100 / 100	720 ms	130872 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 = 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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39