제출 #737533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
737533		esomer	벽 (IOI14_wall)	C++17	100 / 100	938 ms	59300 KiB

wall

#include<bits/stdc++.h>
 
using namespace std;

struct segTree{
	vector<pair<int, int>> v;
	int siz;
	void init(int n){
		siz = 1;
		while(siz < n) siz *= 2;
		v.assign(2 * siz, {0, 0});
	}
	void push(int x){
		v[2 * x + 1].first = min(max(v[2 * x + 1].first, v[x].first), v[x].second);
		v[2 * x + 1].second = max(min(v[2 * x + 1].second, v[x].second), v[x].first);
		v[2 * x + 2].first = min(max(v[2 * x + 2].first, v[x].first), v[x].second);
		v[2 * x + 2].second = max(min(v[2 * x + 2].second, v[x].second), v[x].first);
	}
	void set(int l, int r, int x, int lx, int rx, int h, int t){
		if(lx >= l && rx <= r){
			if(t == 1){
				v[x].first = max(v[x].first, h);
				v[x].second = max(v[x].second, v[x].first);
			}else{
				v[x].second = min(v[x].second, h);
				v[x].first = min(v[x].first, v[x].second);
			}
			return;
		}else if(lx >= r || rx <= l) return;
		push(x);
		v[x] = {0, 100000};
		int m = (lx + rx) / 2;
		set(l, r, 2 * x + 1, lx, m, h, t);
		set(l, r, 2 * x + 2, m, rx, h, t);
	}
	void set(int l, int r, int h, int t){
		set(l, r, 0, 0, siz, h, t);
	}
	int calc(int i, int x, int lx, int rx){
		if(rx - lx == 1){
			return v[x].first;
		}
		push(x);
		v[x] = {0, 100000};
		int m = (lx + rx) / 2;
		if(i < m) return calc(i, 2 * x + 1, lx, m);
		else return calc(i, 2 * x + 2, m, rx);
	}
	int calc(int i){
		return calc(i, 0, 0, siz);
	}
};

//~ int op[1000];
//~ int lft[1000];
//~ int rght[1000];
//~ int height[1000];
//~ int finalHeight[1000];

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

//~ int main(){
	//~ int n, k; cin >> n >> k;
	//~ for(int i = 0; i < k; i++){
		//~ cin >> op[i] >> lft[i] >> rght[i] >> height[i];
	//~ }
	//~ buildWall(n, k);
	//~ for(int i = 0; i < n; i++){
		//~ cout << finalHeight[i] << " ";
	//~ }
//~ }

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