Submission #692982

#	Time	Username	Problem	Language	Result	Execution time	Memory
692982		Pyqe	Radio Towers (IOI22_towers)	C++17	17 / 100	1036 ms	10700 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 nn=0,a[100069],ex[100069],zs=0;
multiset<long long> ms;
priority_queue<pair<long long,pair<long long,long long>>> pq;
bitset<100069> vtd;
pair<long long,long long> sq[100069];

void init(int n,vector<int> aa)
{
	long long i,k,l,w,e=0;
	multiset<long long>::iterator it;
	
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
	}
	a[0]=inf;
	a[n+1]=inf;
	for(i=1;i<=n;i++)
	{
		if(a[i]<a[i-1]&&a[i]<a[i+1])
		{
			if(!e)
			{
				nn++;
				ex[nn]=i;
				e=1;
			}
		}
		else if(a[i]>a[i-1]&&a[i]>a[i+1])
		{
			if(e)
			{
				nn++;
				ex[nn]=i;
				e=0;
			}
		}
	}
	if(!e)
	{
		nn--;
	}
	for(i=1;i<=nn;i++)
	{
		ms.insert(ex[i]);
	}
	for(i=1;i<=nn-1;i++)
	{
		pq.push({-abs(a[ex[i]]-a[ex[i+1]]),{ex[i],ex[i+1]}});
	}
	zs++;
	sq[zs]={0,(nn+1)/2};
	for(;!pq.empty();)
	{
		w=-pq.top().fr;
		k=pq.top().sc.fr;
		l=pq.top().sc.sc;
		pq.pop();
		if(vtd[k]||vtd[l])
		{
			continue;
		}
		zs++;
		sq[zs]={w,sq[zs-1].sc-1};
		ms.erase(k);
		ms.erase(l);
		vtd[k]=1;
		vtd[l]=1;
		it=ms.lower_bound(k);
		if(it==ms.begin())
		{
			continue;
		}
		k=*prev(it);
		it=ms.upper_bound(l);
		if(it==ms.end())
		{
			continue;
		}
		l=*it;
		pq.push({-abs(a[k]-a[l]),{k,l}});
	}
}

int max_towers(int lb,int rb,int cw)
{
	lb++;
	rb++;
	if(lb==rb)
	{
		return 1;
	}
	else
	{
		long long p;
		
		p=lower_bound(sq+1,sq+zs+1,mp((long long)cw,-inf))-sq-1;
		return sq[p].sc;
	}
}

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