제출 #88421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88421		Pajaraja	벽 (IOI14_wall)	C++17	100 / 100	892 ms	164468 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define MAXN 2000007
using namespace std;
int seg[4*MAXN],poz[MAXN];
bool tr[4*MAXN];
void relax(int ind)
{
	if(seg[ind]==-1) return;
	seg[2*ind]=seg[2*ind+1]=seg[ind];
	seg[ind]=-1;
}
void upd(int l,int r,int lt, int rt,int val,bool b,int ind)
{
	if(r<lt || l>rt) return;
	if(l>=lt && r<=rt && seg[ind]!=-1)
	{
		if(b) seg[ind]=max(seg[ind],val);
		else seg[ind]=min(seg[ind],val);
		return;
	}
	relax(ind);
	int s=(l+r)/2;
	upd(l,s,lt,rt,val,b,2*ind); upd(s+1,r,lt,rt,val,b,2*ind+1);
	if(seg[2*ind]==seg[2*ind+1]) seg[ind]=seg[2*ind];
	else seg[ind]=-1; 
}
void loc(int l,int r,int ind)
{
	if(l==r) {poz[l]=ind; tr[ind]=true; return;}
	int s=(l+r)/2; loc(l,s,2*ind); loc(s+1,r,2*ind+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	loc(0,n-1,1);
	for(int i=0;i<k;i++) upd(0,n-1,left[i],right[i],height[i],op[i]==1,1);
	for(int i=1;i<poz[n-1];i++) if(!tr[i]) relax(i);
	for(int i=0;i<n;i++) finalHeight[i]=seg[poz[i]];
}

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