제출 #799695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
799695		IvanJ	벽 (IOI14_wall)	C++17	100 / 100	1388 ms	102408 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

struct Seg {
	int pot;
	vector<ii> T, L;
	void init(int n) {
		pot = 1;
		while(pot < n) pot <<= 1;
		T = vector<ii>(pot << 1, {0, 1e5});
		L = vector<ii>(pot << 1, {0, 1e5});
	}
	
	ii merge(ii f, ii g) {
		ii ret;
		if(g.x >= f.y) return {f.y, f.y};
		if(g.y <= f.x) return {f.x, f.x};
		return {max(g.x, f.x), min(g.y, f.y)};
	}
	
	void prop(int x) {
		T[x] = merge(L[x], T[x]);
		if(x < pot) L[x * 2] = merge(L[x], L[x * 2]);
		if(x < pot) L[x * 2 + 1] = merge(L[x], L[x * 2 + 1]);
		L[x] = {0, 1e5};
	}
	
	void update(int x, int lo, int hi, int a, int b, ii f) {
		prop(x);
		if(hi < a || b < lo) return;
		if(a <= lo && hi <= b) {
			L[x] = merge(f, L[x]);
			prop(x);
			return;
		}
		int mid = (lo + hi) / 2;
		update(x * 2, lo, mid, a, b, f);
		update(x * 2 + 1, mid + 1, hi, a, b, f);
	}
	
	void add(int lo, int hi, ii f) {update(1, 0, pot - 1, lo, hi, f);}
	
	int get(int x) {return T[x + pot].x;}
} S;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	S.init(n);
	for(int i = 0;i < k;i++) {
		if(op[i] == 1) 
			S.add(left[i], right[i], {height[i], 1e5});
		if(op[i] == 2) 
			S.add(left[i], right[i], {0, height[i]});
	}
	for(int i = 0;i < n;i++) 
		S.add(i, i, {0, 1e5});
	for(int i = 0;i < n;i++) 
		finalHeight[i] = S.get(i);
}

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