제출 #1163394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163394		boclobanchat	벽 (IOI14_wall)	C++20	100 / 100	601 ms	59292 KiB

wall

#include"wall.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=2222222;
ii seg[MAXN*4];
bool lazy[MAXN*4];
int n;
ii merge(ii a,ii b)
{
	ii c={max(a.fi,b.fi),min(a.se,b.se)};
	if(c.fi>c.se)
	{
		if(a.fi<b.fi) return {c.fi,c.fi};
		return {c.se,c.se};
	}
	return c;
}
void down(int pos)
{
	seg[pos*2]=merge(seg[pos*2],seg[pos]);
	seg[pos*2+1]=merge(seg[pos*2+1],seg[pos]);
	seg[pos]={0,998244353};
}
void build(int l,int r,int pos)
{
	if(l>r) return ;
	seg[pos]={0,998244353};
	if(l==r)
	{
		seg[pos]={0,0};
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,pos*2);
	build(mid+1,r,pos*2+1);
}
void update(int l,int r,int u,int v,int ck,int val,int pos)
{
	if(v<l||r<u) return ;
	if(u<=l&&r<=v)
	{
		if(!ck) seg[pos]=merge(seg[pos],(ii){val,998244353});
		else seg[pos]=merge(seg[pos],(ii){0,val});
		return ;
	}
	int mid=(l+r)/2;
	down(pos);
	update(l,mid,u,v,ck,val,pos*2);
	update(mid+1,r,u,v,ck,val,pos*2+1);
}
int get(int l,int r,int i,int pos)
{
	if(l==r) return seg[pos].fi;
	int mid=(l+r)/2;
	down(pos);
	if(i<=mid) return get(l,mid,i,pos*2);
	return get(mid+1,r,i,pos*2+1);
}
void build_up(int l,int r,int t)
{
	update(1,n,l+1,r+1,0,t,1);
}
void take_down(int l,int r,int t)
{
	update(1,n,l+1,r+1,1,t,1);
}
int get_height(int i)
{
	return get(1,n,i+1,1);
}
void buildWall(int N,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
	n=N;
	for(int i=0;i<k;i++) if(op[i]==1) build_up(left[i],right[i],height[i]);
	else take_down(left[i],right[i],height[i]);
	for(int i=0;i<n;i++) finalHeight[i]=get_height(i);
}

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