제출 #332108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332108		zggf	Wall (IOI14_wall)	C++14	100 / 100	845 ms	69612 KiB

wall

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

using namespace std;

int pot(int x){
	int tmp = 1;
	while(x){
		x/=2;
		tmp*=2;
	}
	return tmp;
}

vector<pair<int, int>> tree;
int treeSize;

void push(int x){
	if(x>=treeSize) return;
	int pt  = x*2;
	tree[pt].first = max(tree[pt].first, tree[x].first);	
	tree[pt].first = min(tree[pt].first, tree[x].second);	
	tree[pt].second = min(tree[pt].second, tree[x].second);
	tree[pt].second = max(tree[pt].second, tree[x].first);
	pt=x*2+1;
	tree[pt].first = max(tree[pt].first, tree[x].first);	
	tree[pt].first = min(tree[pt].first, tree[x].second);	
	tree[pt].second = min(tree[pt].second, tree[x].second);
	tree[pt].second = max(tree[pt].second, tree[x].first);
	
	tree[x] = {0, 1e9};
}

void update(int a, int b, int v, int t, int q = 0, int r = treeSize-1, int pt = 1){
	if(a==q&&b==r){
		if(t){
			tree[pt].first = max(tree[pt].first, v);	
			tree[pt].second = max(tree[pt].first, tree[pt].second);
		}	
		if(!t){
			tree[pt].second = min(v, tree[pt].second);
			tree[pt].first = min(tree[pt].first, tree[pt].second);	
		}	
		return;
	}	
	
	push(pt);
	int mid = (q+r)/2;
	
	if(a<=mid) update(a, min(b, mid), v, t, q, mid, pt*2);
	if(b>mid) update(max(a, mid+1), b, v, t, mid+1, r, pt*2+1);
}

void ultraPush(int pt){
	if(pt>=treeSize) return;
	
	push(pt);
	ultraPush(pt*2);
	ultraPush(pt*2+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	treeSize = pot(n);	
	tree.resize(treeSize*2+1, {0, 1e9});
	for(int i = 0; i < k; i++){
		update(left[i], right[i], height[i], op[i]==1);	
	}
	ultraPush(1);
	for(int i = 0; i < n; i++){
		finalHeight[i] = tree[i+treeSize].first;	
	}
	return;
}

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