제출 #97255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97255		figter001	벽 (IOI14_wall)	C++14	0 / 100	2 ms	512 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e6+50;

int mx[4*maxn],mn[4*maxn];
int l,r,val,t,h[4*maxn];

void pro(int n){
	if(t == 1){
		mx[n] = max(mx[n],val);
		mn[n] = max(mn[n],val);
	}else{
		mx[n] = min(mx[n],val);
		mn[n] = min(mn[n],val);
	}
}

void pro(int n,int s,int e){
	mn[n] = min(mn[n],mn[n/2]);
	mn[n] = max(mn[n],mx[n/2]);
	mx[n] = max(mx[n],mx[n/2]);
	mx[n] = min(mx[n],mn[n/2]);
}

void update(int n,int s,int e){
	if(s > r || e < l)return;
	if(s >= l && e <= r){
		pro(n);
		return;
	}
	pro(n*2,s,e);
	pro(n*2+1,s,e);
	mn[n] = 1e9;
	mx[n] = 0;
	update(n*2,s,(s+e)/2);
	update(n*2+1,(s+e)/2+1,e);
}

int get(int n,int s,int e){
	if(s > r || e < l)return -1;
	if(s == e)return min(mn[n],mx[n]);
	pro(n*2,s,e);
	pro(n*2+1,s,e);
	mn[n] = 1e9;
	mx[n] = 0;
	return max(get(n*2,s,(s+e)/2) , get(n*2+1,(s+e)/2+1,e));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<k;i++){
		left[i]++;
		right[i]++;
		l = left[i];
		r = right[i];
		val = height[i];
		t = op[i];
		update(1,1,n);
	}
	for(int i=0;i<k;i++){
		l = r = i+1;
		height[i] = get(1,1,n);
	}
	return;
}

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