제출 #77126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77126		FiloSanza	벽 (IOI14_wall)	C++14	61 / 100	1243 ms	263168 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;

struct Segment{
	inline int left(int i){return (i*2)+1;}
	inline int right(int i){return (i+1)*2;}

	vector<int> v;
	vector<int> maxi;
	vector<int> mini;
	int S;

	Segment(int N){
		S = (1<<(int)ceil(log2(N)+1))-1;
		v.resize(S, 0);
		mini.resize(S, INF);
		maxi.resize(S, -INF);
	}

	void check(int pos){
		if(mini[pos] == -INF) return; //mai aggiornato
		v[pos] = max(mini[pos], v[pos]);
		v[pos] = min(maxi[pos], v[pos]);
		if(pos < S/2){
			if(maxi[left(pos)] < mini[pos]) mini[left(pos)] = maxi[left(pos)] = mini[pos];
			if(maxi[pos] < mini[left(pos)]) mini[left(pos)] = maxi[left(pos)] = maxi[pos];
			maxi[left(pos)] = min(maxi[pos], maxi[left(pos)]);
			mini[left(pos)] = max(mini[pos], mini[left(pos)]);
			if(maxi[right(pos)] < mini[pos]) mini[right(pos)] = maxi[right(pos)] = mini[pos];
			if(maxi[pos] < mini[right(pos)]) mini[right(pos)] = maxi[right(pos)] = maxi[pos];
			maxi[right(pos)] = min(maxi[pos], maxi[right(pos)]);
			mini[right(pos)] = max(mini[pos], mini[right(pos)]);
		}

		mini[pos] = -INF;
		maxi[pos] = INF;
	}

	void update(int pos, int a, int b, int l, int r, int mm, int MM){
		if(a > r || b < l)
			return;
		check(pos);
		if(a >= l && b <= r){
			if(maxi[pos] < mm) maxi[pos] = mini[pos] = mm;
			if(mm < mini[pos]) maxi[pos] = mini[pos] = MM;
			maxi[pos] = min(maxi[pos], MM);
			mini[pos] = max(mini[pos], mm);
			check(pos);
			return;
		}
		int mid = (a+b)/2;
		update(left(pos), a, mid, l, r, mm, MM);
		update(right(pos), mid+1, b, l, r, mm, MM);
	}

	void updateAll(){
		for(int i=0; i<S; i++)
			check(i);
	}

	int getAt(int i){
		return v[S/2+i];
	}
};	

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	Segment st(n);
	for(int i=0; i<k; i++){
		if(op[i] == 1)
			st.update(0, 0, st.S/2, left[i], right[i], height[i], INF);
		else
			st.update(0, 0, st.S/2, left[i], right[i], 0, height[i]);
	}
	
	st.updateAll();

	for(int i=0; i<n; i++)
		finalHeight[i] = st.getAt(i) == -INF ? 0 : st.getAt(i);
}

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