Submission #126526

#	Time	Username	Problem	Language	Result	Execution time	Memory
126526		Boxworld	벽 (IOI14_wall)	C++14	100 / 100	775 ms	98440 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int maxN=2000100;
int L,R,H,C;
int Mx[maxN*4],Mi[maxN*4],fH[maxN];
inline int ls(int p){return p*2+1;}
inline int rs(int p){return p*2+2;}
void Max(int p,int k){
	if (Mx[p]<k)Mx[p]=k;
	if (Mi[p]<k)Mi[p]=k;
}
void Min(int p,int k){
	if (Mx[p]>k)Mx[p]=k;
	if (Mi[p]>k)Mi[p]=k;
}
void push_node(int p){
	Max(ls(p),Mx[p]);
	Min(ls(p),Mi[p]);
	Max(rs(p),Mx[p]);
	Min(rs(p),Mi[p]);
	Mx[p]=0;
	Mi[p]=0x7fffffff;
}
void update(int p,int l,int r){
	if (L<=l&&r<=R){
		if (C==1)Max(p,H);
		else Min(p,H);
		return;
	}
	push_node(p);
	int m=(l+r)/2;
	if (L<=m)update(ls(p),l,m);
	if (m<R)update(rs(p),m+1,r);
	return;
}
void query(int p,int l,int r){
	if(l==r){fH[l]=Mx[p];return;}
	int m=(l+r)/2;
	push_node(p);
	query(ls(p),l,m);
	query(rs(p),m+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	memset(Mx,0,sizeof(Mx));
	memset(Mi,0x7f,sizeof(Mi));
	for (int i=0;i<k;i++){
		L=left[i];
		R=right[i];
		H=height[i];
		C=op[i];
		update(0,0,n-1);
	}
	query(0,0,n-1);
	for (int i=0;i<n;i++)finalHeight[i]=fH[i];
	return;
}

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