제출 #377878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377878		YJU	벽 (IOI14_wall)	C++14	0 / 100	62 ms	94316 KiB

wall

#include<bits/stdc++.h>
#include<wall.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=2e6+5;
const ll MOD=1e9+7;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

struct node{
	ll l,r;
}seg[4*N];

node operator +(node A,node B){
	if(A.l>=B.r){
		return node{B.r,B.r};
	}else if(A.r<=B.l){
		return node{B.l,B.l};
	}else{
		assert(max(A.l,B.l)<=min(A.r,B.r));
		return node{max(A.l,B.l),min(A.r,B.r)};
	}
}

void ins(ll id,ll l,ll r,ll to,node del){
	if(l==r-1){seg[id]=del;return ;}
	ll mid=(l+r)>>1;
	if(to<mid){
		ins(id*2,l,mid,to,del);
	}else{
        ins(id*2+1,mid,r,to,del);
	}
	seg[id]=seg[id*2]+seg[id*2+1];
}

vector<ll> app[N],rem[N];

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	REP(i,k){
        ins(1,0,k,i,node{0,INF});
        app[left[i]].pb(i);
        rem[right[i]].pb(i);
	}
	REP(i,n){
		for(ll j:app[i]){
			node tmp;
			if(op[j]==1)tmp=node{height[j],INF};
			else tmp=node{0,height[j]};
            ins(1,0,k,j,tmp);
		}
		for(ll j:rem[i]){
            ins(1,0,k,j,node{0,INF});
		}
		finalHeight[i]=seg[1].l;
	}
	//REP(i,n)cout<<finalHeight[i]<<" \n"[i==n-1];
}
/*
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);

	return 0;
}
//*/

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