제출 #736939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
736939		NeroZein	벽 (IOI14_wall)	C++17	100 / 100	719 ms	77384 KiB

wall

#include "wall.h"
#include "bits/stdc++.h"
using namespace std; 
#define lx (nd * 2)
#define rx (nd * 2 + 1)

const int N = 2000006;

struct node {
	int mn = 0, mx = 0; 
};

node seg[N << 2]; 
int arr[N]; 

void push (int nd) {
	for (int i = lx; i < lx + 2; ++i) {
		seg[i].mn = min(seg[i].mn, seg[nd].mn); 
		seg[i].mn = max(seg[i].mn, seg[nd].mx); 
		seg[i].mx = min(seg[i].mx, seg[nd].mn);
		seg[i].mx = max(seg[i].mx, seg[nd].mx); 
	}
}

void upd (int nd, int l, int r, int s, int e, int v, int op) {
	if (l > e || r < s) {
		return; 
	}
	if (l >= s && r <= e) {
		if (op == 1) {
			seg[nd].mx = max(seg[nd].mx, v); 
			seg[nd].mn = max(seg[nd].mn, v); 
		} else {
			seg[nd].mx = min(seg[nd].mx, v); 
			seg[nd].mn = min(seg[nd].mn, v); 
		}
		return; 
	}
	push(nd);
	seg[nd].mn = N; 
	seg[nd].mx = 0; 
	int mid = (l + r) >> 1;
	upd(lx, l, mid, s, e, v, op);
	upd(rx, mid + 1, r, s, e, v, op); 
}

inline void dive (int nd, int l, int r) {
	if (l == r) {
		arr[l] = seg[nd].mn; 
		assert(seg[nd].mn == seg[nd].mx); 
		return; 
	}
	push(nd); 
	int mid = (l + r) >> 1;
	dive(lx, l, mid);
	dive(rx, mid + 1, r); 
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < k; ++i) {
		upd(1, 0, n - 1, left[i], right[i], height[i], op[i]);
	}	
	dive(1, 0, n - 1); 
	for (int i = 0; i < n; ++i) {
		finalHeight[i] = arr[i]; 
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39