제출 #307287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
307287		tengiz05	벽 (IOI14_wall)	C++17	0 / 100	167 ms	8184 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct segtree {
	struct Node {
		int min;
		int max;
	};
	vector<Node> t;
	int no_max = INT_MAX;
	int no_min = 0;
	int sz;
	void init(int n){
		sz = 1;
		while(sz < n)sz <<= 1;
		t.assign(sz*2, {0, 0});
	}
	void modify(int Max, int Min, int node){
		t[node].max = min(Max, max(Min, t[node].max));
		t[node].min = min(Max, max(Min, t[node].min));
	}
	void push(int node, int len){
		if(len == 1){
			t[node] = {no_min, no_max};
			return;
		}
		modify(t[node].max, t[node].min, node*2);
		modify(t[node].max, t[node].min, node*2+1);
		t[node] = {no_min, no_max};
	}
	
	void add(int l, int r, int L, int R, int node, int Max, int Min){
		if(L >= r || R <= l)return;
		push(node, R-L);
		if(L >= l && R <= r){
			modify(Max, Min, node);
			return;
		}
		int mid = (L+R)/2;
		add(l, r, L, mid, node*2, Max, Min);
		add(l, r, mid, R, node*2+1,Max,Min);
	}
	void add(int l, int r, int Max, int Min){
		add(l, r, 0, sz, 1, Max, Min);
	}
	
	int get(int i, int L, int R, int node){
		if(R-L == 1){
			return t[node].min;
		}
		push(node, R-L);
		int mid = (L+R)/2;
		if(i < mid)return get(i, L, mid, node*2);
		else return get(i, mid, R, node*2+1);
	}int get(int i){
		int ans = max(get(i, 0, sz, 1), 0);
		return ans;
	}
	/*
	void print(){
		cout << '\n';
		for(int i=1;i<sz*2;i++){
			cout << t[i].min << ' ' << t[i].max << '\n';
		}cout << "\n\n";
	}*/
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	segtree seg;
	seg.init(n);
	for(int i=0;i<k;i++){
	//	seg.print();
		if(op[i] == 2){
			// add
			seg.add(left[i], right[i]+1, height[i], seg.no_min);
		}else {
			// remove
			seg.add(left[i], right[i]+1, seg.no_max, height[i]);
		}
	}//seg.print();
	for(int i=0;i<n;i++){
		finalHeight[i] = seg.get(i);
	//	seg.print();
	}
	return;
}

/*

10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0


*/

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