Submission #987162

#	Time	Username	Problem	Language	Result	Execution time	Memory
987162		Pyqe	Radio Towers (IOI22_towers)	C++17	17 / 100	778 ms	13824 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],sq[100069];
multiset<long long> ms;
multiset<pair<long long,pair<long long,long long>>> rg;

void init(int on,vector<int> aa)
{
	long long i,k,l=-1,w,c=0,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;
			c++;
		}
	}
	c=(c+1)/2;
	sq[0]=c;
	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;
		}
		c--;
		udn++;
		uds[udn]=w;
		sq[udn]=c;
		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}});
		}
	}
}

int max_towers(int lb,int rb,int cw)
{
	long long p=lower_bound(uds+1,uds+udn+1,cw)-uds-1;
	
	return sq[p];
}

• 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