Submission #987168

#	Time	Username	Problem	Language	Result	Execution time	Memory
987168		Pyqe	Radio Towers (IOI22_towers)	C++17	100 / 100	1769 ms	170792 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 inf=1e18;
long long n,udn=0,a[100069],uds[100069],sp[17][100069],lg2[100069];
multiset<long long> ms;
multiset<pair<long long,pair<long long,long long>>> rg;
bitset<100069> spc;

struct segtree
{
	long long l,r,sm;
	pair<long long,long long> mxl,mxr;
	segtree *p[2];
	
	void bd(long long lb,long long rb)
	{
		l=lb;
		r=rb;
		if(l==r)
		{
			sm=spc[l];
			mxl={spc[l],-l};
			mxr={spc[l],l};
		}
		else
		{
			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);
			}
			sm=p[0]->sm+p[1]->sm;
			mxl=max(p[0]->mxl,p[1]->mxl);
			mxr=max(p[0]->mxr,p[1]->mxr);
		}
	}
	void ud(long long x,long long w)
	{
		if(l>=x&&r<=x)
		{
			sm+=w;
			mxl.fr+=w;
			mxr.fr+=w;
		}
		else
		{
			long long ii;
			
			for(ii=0;ii<2;ii++)
			{
				if(!(p[ii]->l>x||p[ii]->r<x))
				{
					segtree *tmp=p[ii];
					
					p[ii]=new segtree;
					*p[ii]=*tmp;
					p[ii]->ud(x,w);
				}
			}
			sm=p[0]->sm+p[1]->sm;
			mxl=max(p[0]->mxl,p[1]->mxl);
			mxr=max(p[0]->mxr,p[1]->mxr);
		}
	}
	long long qrs(long long lb,long long rb)
	{
		if(l>rb||r<lb)
		{
			return 0;
		}
		else if(l>=lb&&r<=rb)
		{
			return sm;
		}
		else
		{
			return p[0]->qrs(lb,rb)+p[1]->qrs(lb,rb);
		}
	}
	pair<long long,long long> qrxl(long long lb,long long rb)
	{
		if(l>rb||r<lb)
		{
			return {-inf,-1};
		}
		else if(l>=lb&&r<=rb)
		{
			return mxl;
		}
		else
		{
			return max(p[0]->qrxl(lb,rb),p[1]->qrxl(lb,rb));
		}
	}
	pair<long long,long long> qrxr(long long lb,long long rb)
	{
		if(l>rb||r<lb)
		{
			return {-inf,-1};
		}
		else if(l>=lb&&r<=rb)
		{
			return mxr;
		}
		else
		{
			return max(p[0]->qrxr(lb,rb),p[1]->qrxr(lb,rb));
		}
	}
}
sg[100069];

inline void spbd()
{
	long long i,j,k;
	
	for(i=1;i<=n;i++)
	{
		sp[0][i]=a[i];
	}
	for(i=1;1ll<<i<=n;i++)
	{
		for(j=1;j<=n-(1ll<<i)+1;j++)
		{
			sp[i][j]=min(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
		}
	}
	for(i=1;i<=n;i++)
	{
		for(k=i;k>1;k/=2,lg2[i]++);
	}
}

inline long long spqr(long long lb,long long rb)
{
	if(lb<=rb)
	{
		long long e=lg2[rb-lb+1];
		
		return min(sp[e][lb],sp[e][rb-(1ll<<e)+1]);
	}
	else
	{
		return inf;
	}
}

void init(int on,vector<int> aa)
{
	long long i,k,l=-1,w,k2,l2;
	
	n=on;
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
	}
	ms.insert(-inf);
	ms.insert(inf);
	for(i=1;i<=n;i++)
	{
		if(((i==1||a[i]<a[i-1])&&(i==n||a[i]<a[i+1]))||(i>1&&i<n&&a[i]>max(a[i-1],a[i+1])))
		{
			ms.insert(i);
			if(l!=-1)
			{
				rg.insert({abs(a[l]-a[i]),{l,i}});
			}
			l=i;
			spc[i]=1;
		}
	}
	sg[0].bd(1,n);
	for(;!rg.empty();)
	{
		w=rg.begin()->fr;
		k=rg.begin()->sc.fr;
		l=rg.begin()->sc.sc;
		rg.erase(rg.begin());
		if(ms.find(k)==ms.end()||ms.find(l)==ms.end())
		{
			continue;
		}
		ms.erase(k);
		ms.erase(l);
		k2=*prev(ms.lower_bound(k));
		l2=*ms.upper_bound(l);
		if(k2!=-inf&&l2!=inf)
		{
			rg.insert({abs(a[k2]-a[l2]),{k2,l2}});
		}
		udn++;
		uds[udn]=w;
		sg[udn]=sg[udn-1];
		sg[udn].ud(k,-1);
		sg[udn].ud(l,-1);
	}
	spbd();
}

int max_towers(int lb,int rb,int cw)
{
	long long k,w,w2,w3,p,mn,z;
	pair<long long,long long> tmp;
	
	lb++;
	rb++;
	p=lower_bound(uds+1,uds+udn+1,cw)-uds-1;
	w=sg[p].sm;
	w2=sg[p].qrs(1,lb-1);
	w3=sg[p].qrs(rb+1,n);
	z=(max(w-(w2+1)/2*2-(w3+1)/2*2,0ll)+1)/2;
	if(w2%2)
	{
		tmp=sg[p].qrxl(lb,rb);
		if(tmp.fr)
		{
			k=-tmp.sc;
			mn=spqr(lb,k-1);
			z+=a[k]-mn>=cw;
		}
	}
	if(w3%2)
	{
		tmp=sg[p].qrxr(lb,rb);
		if(tmp.fr)
		{
			k=tmp.sc;
			mn=spqr(k+1,rb);
			z+=a[k]-mn>=cw;
		}
	}
	z=max(z,1ll);
	return z;
}

Compilation message (stderr)

towers.cpp: In function 'void spbd()':
towers.cpp:134:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  134 |    sp[i][j]=min(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
      |                                            ~^~

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