Submission #693062

#	Time	Username	Problem	Language	Result	Execution time	Memory
693062		Pyqe	Radio Towers (IOI22_towers)	C++17	0 / 100	1651 ms	396048 KiB

towers

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long mm=17,ma=1e9,inf=1e18;
long long n,nn=0,rt,a[100069],sk[100069],sk2[100069],al[100069][2],sbt[100069],dh[100069],an[100069],pr[100069],peu[100069],wg[3][100069],bl[100069][mm];
vector<long long> al2[100069];
pair<long long,long long> as[3][100069];

struct segtree
{
	long long l,r,sm;
	segtree *p[2];
	
	void bd(long long lh,long long rh)
	{
		l=lh;
		r=rh;
		sm=0;
		if(l<r)
		{
			long long ii,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 ud(long long x,long long w)
	{
		if(l>=x&&r<=x)
		{
			sm+=w;
		}
		else
		{
			long long ii;
			segtree *tmp;
			
			for(ii=0;ii<2;ii++)
			{
				if(!(p[ii]->l>x||p[ii]->r<x))
				{
					tmp=p[ii];
					p[ii]=new segtree;
					*p[ii]=*tmp;
					p[ii]->ud(x,w);
				}
			}
			sm=p[0]->sm+p[1]->sm;
		}
	}
	long long qr(long long lh,long long rh)
	{
		if(l>rh||r<lh)
		{
			return 0;
		}
		else if(l>=lh&&r<=rh)
		{
			return sm;
		}
		else
		{
			return p[0]->qr(lh,rh)+p[1]->qr(lh,rh);
		}
	}
}
sg[4][100069];

void bd(long long x)
{
	long long i,ii,l,e;
	pair<long long,long long> mxe={-inf,-1};
	
	sbt[x]=1;
	an[x]=x;
	for(ii=0;ii<2;ii++)
	{
		l=al[x][ii];
		if(l)
		{
			dh[l]=dh[x]+1;
			pr[l]=x;
			bd(l);
			sbt[x]+=sbt[l];
			al2[x].push_back(l);
			mxe=max(mxe,{sbt[l],al2[x].size()-1});
		}
	}
	e=mxe.sc;
	if(e!=-1)
	{
		swap(al2[x][0],al2[x][e]);
	}
	bl[x][0]=pr[x];
	for(i=1;i<=mm;i++)
	{
		bl[x][i]=bl[bl[x][i-1]][i-1];
	}
}

void bd2(long long x)
{
	long long i,sz=al2[x].size(),l;
	
	if(sz)
	{
		an[al2[x][0]]=an[x];
	}
	n++;
	peu[x]=n;
	for(i=0;i<sz;i++)
	{
		l=al2[x][i];
		bd2(l);
	}
}
 
void init(int on,vector<int> aa)
{
	long long i,ii,u,k,l;
	
	n=on;
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
		l=-1;
		for(;nn&&a[sk[nn]]>a[i];nn--)
		{
			l=sk[nn];
		}
		if(l!=-1)
		{
			al[i][0]=l;
		}
		if(nn)
		{
			al[sk[nn]][1]=i;
		}
		nn++;
		sk[nn]=i;
	}
	rt=sk[1];
	bd(rt);
	n=0;
	bd2(rt);
	for(ii=0;ii<2;ii++)
	{
		u=!ii*2-1;
		nn=0;
		sk2[0]=ma;
		for(i=1+(n-1)*ii;i&&i<=n;i+=u)
		{
			for(;nn&&a[sk[nn]]>a[i];nn--)
			{
				sk2[nn-1]=max(sk2[nn-1],sk2[nn]);
			}
			wg[ii][i]=max(sk2[nn]-a[i],0ll);
			nn++;
			sk[nn]=i;
			sk2[nn]=a[i];
		}
	}
	for(i=1;i<=n;i++)
	{
		wg[2][i]=min(wg[0][i],wg[1][i]);
	}
	for(ii=0;ii<3;ii++)
	{
		for(i=1;i<=n;i++)
		{
			as[ii][i]={wg[ii][i],i};
		}
		sort(as[ii]+1,as[ii]+n+1);
		sg[ii][0].bd(1,n);
		for(i=1;i<=n;i++)
		{
			k=as[ii][i].sc;
			sg[ii][i]=sg[ii][i-1];
			sg[ii][i].ud(peu[k],1);
		}
	}
	sg[3][0].bd(1,n);
	for(i=1;i<=n;i++)
	{
		k=as[2][i].sc;
		sg[3][i]=sg[3][i-1];
		sg[3][i].ud(k,1);
	}
}

long long qr2(long long xx,long long lh,long long rh,long long cw)
{
	return sg[xx][cw].qr(lh,rh);
}

long long pth(long long x,long long xx,long long lh,long long rh,long long cw,bool kd)
{
	long long i,p,z=0;
	
	for(;1;x=pr[an[x]])
	{
		if(pr[an[x]]<lh||pr[an[x]]>rh)
		{
			break;
		}
		z+=sg[xx][cw].qr(peu[an[x]],peu[x]);
	}
	p=x;
	for(i=mm-1;i>=0;i--)
	{
		if(bl[p][i]>=lh&&bl[p][i]<=rh)
		{
			p=bl[p][i];
		}
	}
	z+=sg[xx][cw].qr(peu[p]+!kd,peu[x]);
	return z;
}

int max_towers(int lb,int rb,int cw)
{
	long long ii,p[3],z;
	
	lb++;
	rb++;
	z=rb-lb+1;
	for(ii=0;ii<3;ii++)
	{
		p[ii]=lower_bound(as[ii]+1,as[ii]+n+1,mp((long long)cw,-inf))-as[ii]-1;
	}
	z-=qr2(3,lb,rb,p[2]);
	z+=pth(lb,2,lb,rb,p[2],1);
	z-=pth(lb,1,lb,rb,p[1],0);
	z+=pth(rb,2,lb,rb,p[2],0);
	z-=pth(rb,0,lb,rb,p[0],0);
	return z;
}

Compilation message (stderr)

towers.cpp: In function 'void bd(long long int)':
towers.cpp:106:11: warning: iteration 16 invokes undefined behavior [-Waggressive-loop-optimizations]
  106 |   bl[x][i]=bl[bl[x][i-1]][i-1];
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
towers.cpp:104:11: note: within this loop
  104 |  for(i=1;i<=mm;i++)
      |          ~^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23