제출 #1065116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1065116		Edu175	벽 (IOI14_wall)	C++17	100 / 100	878 ms	120420 KiB

wall

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto kjfg:v)cout<<kjfg<<" ";cout<<"\n";}
using namespace std;
typedef int ll;
typedef pair<ll,ll> ii;
const ll INF=1e5+5;
typedef ll tn; // node type
typedef ii tl; // lazy type
// tn unit(ll v){return v;}
#define NEUT 0
tl CLEAR={-1,INF}; // cleared lazy node
tn oper(tn a, tn b){
	return max(a,b);
}
void acum(tl &a, tl v){ // accumulate lazy node
	auto [l,r]=a;
	auto [l2,r2]=v;
	if(l2>=r)a={l2,l2};
	else if(r2<=l)a={r2,r2};
	else a={max(l,l2),min(r,r2)};
}
tn calc(ll s, ll e, tn a, tl v){ // calculate STree range, a=previous value
	a=max(a,v.fst);
	a=min(a,v.snd);
	return a;
} 
struct STree{
	vector<tn>st; vector<tl>lazy; ll n;
	STree(ll n):st(4*n+5,NEUT),lazy(4*n+5,CLEAR),n(n){}
	void push(ll k, ll s, ll e){
		if(lazy[k]==CLEAR)return;
		st[k]=calc(s,e,st[k],lazy[k]);
		if(e-s!=1){
			acum(lazy[2*k],lazy[k]);
			acum(lazy[2*k+1],lazy[k]);
		}
		lazy[k]=CLEAR;
	}
	void upd(ll k, ll s, ll e, ll a, ll b, tl v){ // range update
		push(k,s,e);
		if(e<=a||b<=s)return;
		if(a<=s&&e<=b){
			acum(lazy[k],v);
			push(k,s,e);
			return;
		}
		ll m=(s+e)/2;
		upd(2*k,s,m,a,b,v),upd(2*k+1,m,e,a,b,v);
		st[k]=oper(st[2*k],st[2*k+1]);
	}
	tn query(ll k, ll s, ll e, ll a, ll b){
		if(e<=a||b<=s)return NEUT;
		push(k,s,e);
		if(a<=s&&e<=b)return st[k];
		ll m=(s+e)/2;
		return oper(query(2*k,s,m,a,b),query(2*k+1,m,e,a,b));
	}
	void upd(ll a, ll b, tl v){upd(1,0,n,a,b,v);}
	tn query(ll a, ll b){return query(1,0,n,a,b);}
};
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ret[]){
	STree st(n);
	fore(i,0,q){
		r[i]++,op[i]--;
		tl v;
		if(op[i]==0)v={h[i],INF};
		else v={-1,h[i]};
		st.upd(l[i],r[i],v);
	}
	// fore(i,0,q){
	// 	fore(j,l[i],r[i]){
	// 		if(op[i]==1)a[j]=max(a[j],h[i]);
	// 		else a[j]=min(a[j],h[i]);
	// 	}
	// }
	fore(i,0,n)ret[i]=st.query(i,i+1);
}

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