Submission #693013

#	Time	Username	Problem	Language	Result	Execution time	Memory
693013		Pyqe	Radio Towers (IOI22_towers)	C++17	23 / 100	4066 ms	2640 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 a[100069],ps[100069];
 
void init(int n,vector<int> aa)
{
	long long i;
	
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
	}
	for(i=1;i<=n;i++)
	{
		ps[i]=ps[i-1]+(i>1&&i<n&&a[i]<a[i-1]&&a[i]<a[i+1]);
	}
}

int max_towers(int lb,int rb,int cw)
{
	lb++;
	rb++;
	if(lb==rb)
	{
		return 1;
	}
	else
	{
		long long i,j,mn,mx,z=ps[rb-1]-ps[lb]+(a[lb]<a[lb+1])+(a[rb]<a[rb-1]);
		
		for(i=lb;i<=rb;i++)
		{
			if((i==lb&&a[i]<a[i+1])||(i==rb&&a[i]<a[i-1])||(i>lb&&i<rb&&a[i]<a[i-1]&&a[i]<a[i+1]))
			{
				mn=inf;
				mx=-inf;
				for(j=i-1;j>=lb;j--)
				{
					if(a[j]<a[i])
					{
						break;
					}
					mx=max(mx,a[j]);
				}
				if(j>=lb)
				{
					mn=min(mn,mx);
				}
				mx=-inf;
				for(j=i+1;j<=rb;j++)
				{
					if(a[j]<a[i])
					{
						break;
					}
					mx=max(mx,a[j]);
				}
				if(j<=rb)
				{
					mn=min(mn,mx);
				}
				if(mn-a[i]<cw)
				{
					z--;
				}
			}
		}
		return z;
	}
}

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