Submission #307239

#	Time	Username	Problem	Language	Result	Execution time	Memory
307239		tengiz05	Wall (IOI14_wall)	C++17	0 / 100	189 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_min = INT_MAX;
	int no_max = INT_MIN;
	int sz;
	void init(int n){
		sz = 1;
		while(sz < n)sz <<= 1;
		t.assign(sz*2, {no_min, no_max});
	}
	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)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);
		if(ans == no_min)ans=0;
		return ans;
	}
};
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++){
		if(op[i] == 1){
			// 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]);
		}
	}
	for(int i=0;i<n;i++){
		finalHeight[i] = seg.get(i);
	}
	return;
}

/*

10 2
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