제출 #530780

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530780		PoPularPlusPlus	벽 (IOI14_wall)	C++17	100 / 100	906 ms	59260 KiB

wall

#include <bits/stdc++.h>

using namespace std;

#include "wall.h"

struct item {
	int rem , fin;
};

struct Seg {
	int siz;
	vector<item> sum;
	
	item nutral = {INT_MAX , 0};
	
	item merge(item a , item b){
		item ans;
		ans.fin = max(a.fin , min(b.fin , a.rem));
		ans.rem = min(a.rem , b.rem);
		return ans;
	}
	
	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;
		sum.assign(siz * 2 , nutral);
	}
	
	int set(int i , int x , int lx , int rx){
		if(rx - lx == 1){
			return sum[x].fin;
		}
		sum[2 * x + 1] = merge(sum[x] , sum[2 * x + 1]);
		sum[2 * x + 2] = merge(sum[x] , sum[2 * x + 2]);
		sum[x] = nutral;
		int m = (lx + rx)/2;
		if(i < m)return set(i , 2 * x + 1 , lx , m);
		else return set(i , 2 * x + 2  , m , rx);
	}
	
	int set(int i){
		return set(i , 0 , 0 , siz);
	}
	
	void range_set(int l, int r , int op , int h , int x , int lx , int rx){
		if(rx <= l || lx >= r){
			return;
		}
		if(lx >= l && rx <= r){
			if(op == 2){
				sum[x].fin = min(sum[x].fin , h);
				sum[x].rem = min(sum[x].rem , h);
			}
			else sum[x].fin = max(sum[x].fin , h);
			return;
		}
		sum[2 * x + 1] = merge(sum[x] , sum[2 * x + 1]);
		sum[2 * x + 2] = merge(sum[x] , sum[2 * x + 2]);
		sum[x] = nutral;
		int m = (lx + rx)/2;
		range_set(l , r , op , h , 2 * x + 1 , lx , m);
		range_set(l ,r , op , h , 2 * x + 2 , m, rx);
	}
	
	void range_set(int l , int r , int op , int h){
		range_set(l , r , op , h , 0 , 0 , siz);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int hei[], int finalHeight[]){
  Seg st;
  st.init(n);
  for(int i = 0; i < k; i++){
	  st.range_set(left[i] , right[i]+1 , op[i] , hei[i]);
  }
  for(int i = 0; i < n; i++)finalHeight[i] = st.set(i);
}

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