Submission #986361

#	Time	Username	Problem	Language	Result	Execution time	Memory
986361		Pyqe	Wall (IOI14_wall)	C++17	100 / 100	789 ms	232496 KiB

wall

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

using namespace std;

int sq[2000069],inf=1e9;

struct segtree
{
	int l,r,lz[2];
	segtree *p[2];
	
	void bd(int lh,int rh)
	{
		int ii;
		
		l=lh;
		r=rh;
		lz[0]=-inf;
		lz[1]=inf;
		if(l==r)
		{
			for(ii=0;ii<2;ii++)
			{
				lz[ii]=0;
			}
		}
		else
		{
			int md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
		}
	}
	void ad(int ky,int w)
	{
		int ii,u=!ky*2-1;
		
		for(ii=0;ii<2;ii++)
		{
			lz[ii]=max(lz[ii]*u,w*u)*u;
		}
	}
	void blc()
	{
		int ii,iii;
		
		for(ii=0;ii<2;ii++)
		{
			for(iii=0;iii<2;iii++)
			{
				p[ii]->ad(iii,lz[iii]);
			}
		}
		lz[0]=-inf;
		lz[1]=inf;
	}
	void ud(int ky,int lh,int rh,int w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			ad(ky,w);
		}
		else
		{
			int ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(ky,lh,rh,w);
			}
		}
	}
	void trv()
	{
		if(l==r)
		{
			sq[l]=lz[0];
		}
		else
		{
			int ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->trv();
			}
		}
	}
}
sg;

void buildWall(int n,int t,int kya[],int la[],int ra[],int wg[],int sqq[])
{
	int rr,i;
	
	sg.bd(0,n-1);
	for(rr=0;rr<t;rr++)
	{
		sg.ud(kya[rr]-1,la[rr],ra[rr],wg[rr]);
	}
	sg.trv();
	for(i=0;i<n;i++)
	{
		sqq[i]=sq[i];
	}
}

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