제출 #294489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
294489		Hemimor	벽 (IOI14_wall)	C++14	100 / 100	794 ms	67836 KiB

wall

#include "wall.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Lazy_Segment_Tree{
	private:
	int n;
	vp date;
	int f(int x,P p){
		if(x<p.first) return p.first;
		if(p.second<x) return p.second;
		return x;
	}
	void Set_Lazy(int k,P p){
		date[k]={f(date[k].first,p),f(date[k].second,p)};
	}
	void Push(int k){
		Set_Lazy(k*2+1,date[k]);
		Set_Lazy(k*2+2,date[k]);
		date[k]={-inf,inf};
	}
	void Rec(int a,int b,int k,int l,int r,P p){
		if(r<=a||b<=l) return;
		if(a<=l&&r<=b){
			Set_Lazy(k,p);
			return;
		}
		Push(k);
		int m=(l+r)/2;
		Rec(a,b,k*2+1,l,m,p);
		Rec(a,b,k*2+2,m,r,p);
	}
	public:
	Lazy_Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vp(2*n-1,{-inf,inf});
	}
	void Query(int a,int b,P p){
		return Rec(a,b,0,0,n,p);
	}
	vi Open(){
		vi a(n);
		for(int i=0;i<n-1;i++) Push(i);
		for(int i=0;i<n;i++) a[i]=f(0,date[i+n-1]);
		return a;
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	Lazy_Segment_Tree st(n);
	for(int i=0;i<k;i++){
		if(op[i]==1) st.Query(left[i],right[i]+1,{height[i],inf});
		else st.Query(left[i],right[i]+1,{-inf,height[i]});
	}
	vi a=st.Open();
	for(int i=0;i<n;i++) finalHeight[i]=a[i];
}

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