Submission #1216308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216308		pbear289	Wall (IOI14_wall)	C++20	100 / 100	1206 ms	235208 KiB

wall

#include <cstdint>
#include <numeric>
#include <utility>
#include <vector>
#include "wall.h"
namespace segment_tree {
	enum class query_type {UPD, SET, NONE};
	template<typename T> struct query {query_type q=query_type::NONE; T v;};
	template<typename T> struct node {T v; int64_t parent{-1}; int64_t l_child{-1}; int64_t r_child{-1}; int64_t len{1}; query<T> q;};
	template<typename T,class comb,class upd=comb>
	class lazy_tree {
	public:
		// i'm so happy i can do this
		lazy_tree(int64_t n_=0,comb f_=comb(),upd g_=upd()):f(f_),g(g_),n(n_) {
			seg.resize(2*n);
			for(int64_t i=1;i<n;++i) {
				seg[i].parent=i/2;
				seg[i].l_child=2*i;
				seg[i].r_child=2*i+1;
			}
			seg[0].l_child=1;
			for(int64_t i=n;i<2*n;++i) {seg[i].parent=i/2;}
			for(int64_t i=n-1;i>=1;--i) {
				seg[i].len=seg[seg[i].l_child].len+seg[seg[i].r_child].len;
			}
			for(int64_t i=0;i<2*n;++i) {seg[i].v=id; seg[i].q.v=id;}
		}
		void update(int64_t a,int64_t b,T v) {__update_r_(0,n-1,seg[0].l_child,a,b,{query_type::UPD,v});}
		void set(int64_t a,int64_t b,T v) {__update_r_(0,n-1,seg[0].l_child,a,b,{query_type::SET,v});}
		T range_query(int64_t a,int64_t b) {return __query_r_(a,b,seg[0].l_child,0,n-1);}
		std::vector<node<T>> full_tree() {return seg;}
	private:
		// we assume that f and g share the same identity, otherwise we're a bit cooked
		comb f; upd g; int64_t n{0}; const T id{f.id};
		std::vector<node<T>> seg; 
		void __apply_(int64_t ptr,const query<T> &x) {
			if(x.q==query_type::UPD) {
				if(seg[ptr].q.q!=query_type::SET) {
					seg[ptr].q=query<T>({query_type::UPD,g(seg[ptr].q.v,x.v)});
				} else {
					seg[ptr].q=query<T>({query_type::SET,g(seg[ptr].q.v,x.v)});
				}
				seg[ptr].v=g(seg[ptr].v,x.v,seg[ptr].len);
			} else if(x.q==query_type::SET) {
				seg[ptr].v=g(id,x.v,seg[ptr].len);
				seg[ptr].q=x;
			} else {}
		}
		void __push_down_(int64_t ptr) {
			if(seg[ptr].l_child!=-1) {
				__apply_(seg[ptr].l_child,seg[ptr].q);
				__apply_(seg[ptr].r_child,seg[ptr].q);
			} else {}
			seg[ptr].q=query<T>();
			seg[ptr].q.v=id;
		}
		void __update_r_(int64_t l,int64_t r,int64_t k,int64_t ql,int64_t qr,const query<T> &x) {
			if(qr<l||ql>r) {return;}
			if(ql<=l&&r<=qr) {
				__apply_(k,x);
			} else {
				__push_down_(k);
				int m=l+seg[seg[k].l_child].len-1;
				__update_r_(l,m,seg[k].l_child,ql,qr,x);
				__update_r_(m+1,r,seg[k].r_child,ql,qr,x);
				seg[k].v=f(seg[seg[k].l_child].v,seg[seg[k].r_child].v);
			}
		}
		T __query_r_(int64_t a,int64_t b,int64_t k,int64_t x,int64_t y) {
			if(b<x||a>y) {return id;}
			if(a<=x&&y<=b) {return seg[k].v;}
			__push_down_(k);
			int d=x+seg[seg[k].l_child].len-1;
			return f(__query_r_(a,b,seg[k].l_child,x,d),__query_r_(a,b,seg[k].r_child,d+1,y));
		}
	};
};
template<typename T> using pmmx=std::pair<T,T>;
// here, we represent a modification as f_{a,b}(x)=min(max(x,a),b); setting elements to c also corresponds to such an operation; in this case we let a=b=c.
template<typename T>
class minmax {
public:
	pmmx<T> operator()(pmmx<T> a,pmmx<T> b,int k=1) {
		if(a.first>a.second) {a.first=a.second;}
		if(b.first>b.second) {b.first=b.second;}
		if(a.first<=b.first&&b.first<=a.second&&a.second<=b.second) {
			return {b.first,a.second};
		} else if(b.first<=a.first&&a.first<=b.second&&b.second<=a.second) {
			return {a.first,b.second};
		} else if(a.first<=b.first&&b.first<=b.second&&b.second<=a.second) {
			return b;
		} else if(b.first<=a.first&&a.first<=a.second&&a.second<=b.second) {
			return a;
		} else if(b.first<=b.second&&b.second<=a.first&&a.first<=a.second) {
			return {b.second,b.second};
		} else if(a.first<=a.second&&a.second<=b.first&&b.first<=b.second) {
			return {b.first,b.first};
		} else {
			return {0,0};
		}
	}
	const pmmx<T> id{pmmx{std::numeric_limits<T>::min(),std::numeric_limits<T>::max()}};
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	segment_tree::lazy_tree<pmmx<int>,minmax<int>> segtree(n);
	for(int i=0;i<k;++i) {
		if(op[i]==1) {
			segtree.update(left[i],right[i],{height[i],std::numeric_limits<int>::max()});
		} else {
			segtree.update(left[i],right[i],{std::numeric_limits<int>::min(),height[i]});
		}
	}
	pmmx<int> func;
	for(int i=0;i<n;++i) {
		func=segtree.range_query(i,i);
		finalHeight[i]=std::min(std::max(0,func.first),func.second);
	}
}

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