제출 #246971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246971		Evirir	벽 (IOI14_wall)	C++17	100 / 100	1462 ms	147884 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(int &a, int b){ a=min(a,b); }
void amax(int &a, int b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e9);
const int MOD = 998244353;

bool DEBUG = 1;
const int MAXN = 2000005;

struct Node {
	int mn = 0, mx = INF;
};

class LazySegmentTree {
private:
	vector<Node> v, lazy;
	int size_;
	
	void update(int s, int e, const Node &val, int k, int l, int r)
	{
		push(k, l, r);
		if(r < s || e < l) return;
		if(s <= l && r <= e){
			lazy[k] = val;
			push(k, l, r);
			return;
		}
		
		int mid = (l+r)>>1;
		update(s, e, val, 2*k, l, mid);
		update(s, e, val, 2*k+1, mid+1, r);
	}
	
	Node query(int s, int e, int k, int l, int r)
	{
		push(k, l, r);
		if(r < s || e < l) return Node{-1,INF}; //dummy value
		if(s <= l && r <= e) return v[k];
		
		int mid = (l+r)/2;
		Node lc = query(s, e, 2*k, l, mid);
		Node rc = query(s, e, 2*k+1, mid+1, r);
		return merge(lc, rc);
	}

public:
	LazySegmentTree(): v(vector<Node>()), lazy(vector<Node>()){}
	LazySegmentTree(int n_){
		for(size_=1;size_<n_;) size_<<=1;
		v.resize(4*size_, Node{0,INF});
		lazy.resize(4*size_, Node{-1,INF});
	}
	
	void push(int k, int l, int r){
		if(lazy[k].mn != -1 || lazy[k].mx != INF){
			if(lazy[k].mn != -1){
				amax(v[k].mn, lazy[k].mn);
				amax(v[k].mx, lazy[k].mn);
			}
			if(lazy[k].mx != INF)
			{
				amin(v[k].mn, lazy[k].mx);
				amin(v[k].mx, lazy[k].mx);
			}
			
			if(l != r){
				mergelazy(lazy[k*2], lazy[k]);
				mergelazy(lazy[k*2+1], lazy[k]);
			}
			lazy[k] = Node{-1,INF};
		}
	}
	
	inline Node merge(const Node &a, const Node &b){
		return Node{(a.mn != -1 ? a.mn : b.mn), (a.mx != INF ? a.mx : b.mx)};
	}
	
	inline void mergelazy(Node &a, const Node &b){
		amax(a.mn, b.mn);
		amax(a.mx, b.mn);
		amin(a.mn, b.mx);
		amin(a.mx, b.mx);
	}
	
	inline void update(int s, int e, const Node &val){
		update(s, e, val, 1, 0, size_-1);
	}
	
	inline Node query(int s, int e){
		return query(s, e, 1, 0, size_-1);
	}
};

void buildWall(int n, int K, int op[], int L[], int R[], int H[], int ans[])
{
	LazySegmentTree st(n);
	
	for(int i=0;i<K;i++)
	{
		if(op[i]==1) st.update(L[i],R[i],Node{H[i],INF});
		else st.update(L[i],R[i],Node{-1,H[i]});
	}
	
	forn(i,0,n) ans[i] = st.query(i,i).mn;
}

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