Submission #480641

#	Time	Username	Problem	Language	Result	Execution time	Memory
480641		Haidara	Wall (IOI14_wall)	C++17	0 / 100	150 ms	21800 KiB

wall

#include<bits/stdc++.h>
#include<wall.h> 
#define v(i) vector< i >
using namespace std;
const int maxn=200200;
int n;
struct node
{
	int mx,mn,lazy;
	node():mx(0),mn(0){}
}st[maxn*4];
void pull(int inx,int l,int r,int val=0)
{
	if(val>0)
	{
		st[inx].mn=val;
		st[inx].mx=max(st[inx].mx,val);
	}
	else if(val<0)
	{
		st[inx].mx=val;
		st[inx].mn=min(val,st[inx].mn);
	}
	if(l!=r)
	{
		st[inx*2].mn=max(st[inx].mn,min(st[inx*2].mn,st[inx].mx));
		st[inx*2].mx=min(st[inx].mx,max(st[inx*2].mx,st[inx].mn));
		st[inx*2+1].mn=max(st[inx].mn,min(st[inx*2+1].mn,st[inx].mx));
		st[inx*2+1].mx=min(st[inx].mx,max(st[inx*2+1].mx,st[inx].mn));
	}
}
void push_up(int inx)
{
	st[inx].mn=min(st[inx*2].mn,st[inx*2+1].mn);
	st[inx].mx=max(st[inx*2].mx,st[inx*2+1].mx);
}
void add(int ql,int qr,int val,int l=0,int r=n-1,int inx=1)
{
	pull(inx,l,r);
	if(ql<=l&&r<=qr)
	{
		pull(inx,l,r,val);
		return ;
	}
	if(ql>r||l>qr)
		return ;
	int mid=l+(r-l)/2;
	add(ql,qr,val,l,mid,inx*2);
	add(ql,qr,val,mid+1,r,inx*2+1);
	push_up(inx);
}
void del(int ql,int qr,int val,int l=0,int r=n-1,int inx=1)
{
	pull(inx,l,r);
	if(ql<=l&&r<=qr)
	{
		pull(inx,l,r,-val);
		return ;
	}
	if(ql>r||l>qr)
		return ;
	int mid=l+(r-l)/2;
	del(ql,qr,val,l,mid,inx*2);
	del(ql,qr,val,mid+1,r,inx*2+1);
	push_up(inx);
}
int query(int pos,int l=0,int r=n-1,int inx=1)
{
	pull(inx,l,r);
	if(l==r)
		return st[inx].mn;
	int mid=l+(r-l)/2;
	int res;
	if(pos<=mid)
		res=query(pos,l,mid,inx*2);
	else 
		res=query(pos,mid+1,r,inx*2+1);
	push_up(inx);
	return res;
}
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)
			add(left[i],right[i],height[i]);
		else 
			del(left[i],right[i],height[i]);
	}
	for(int i=0;i<n;i++)
		finalHeight[i]=query(i);
}

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