Submission #814250

#	Time	Username	Problem	Language	Result	Execution time	Memory
814250		LIF	Radio Towers (IOI22_towers)	C++17	23 / 100	4089 ms	11664 KiB

towers

#include "towers.h"
#include <vector>
#include <stack>
#include <bits/stdc++.h>
using namespace std;
int n;
pair <int,int> aa[300005];
int b[300005];
int rightD[300005];
int leftD[300005];
void init(int N, std::vector<int> H)
{
	n = N;
	for(int i=0;i<H.size();i++)
	{
		aa[i+1].first = H[i];
		aa[i+1].second = i+1;
		b[i+1] = H[i];
	}
	sort(aa+1,aa+n+1);
	for(int i=N;i>=1;i--)
	{
		rightD[i] = N+1;
		leftD[i] = 0;
	}
	return;
}
int lowbit(int x)
{
	return x & (-x);
}
int su[300005];
void change(int x,int add)
{
	while(x <= n)
	{
		su[x] += add;
		x += lowbit(x);				
	}
}
int query(int x)
{
	int ans = 0;
	while(x > 0)
	{
		ans += su[x];
		x -= lowbit(x);
	}
	return ans;
}
int ask(int l,int r)
{
	return query(r) - query(l-1);
}
int st[200005][22];
int findmax(int l,int r)
{
	if(l > r)return -1e9;
	if(r <= 0 || l >= n+1)return -1e9;
	int xx = log(r-l+1) / log(2);
	
	return max(st[l][xx],st[r-(1<<xx)+1][xx]);
}
int max_towers(int L, int R, int D)
{
	L += 1;R += 1;
	for(int i=1;i<=n;i++)st[i][0] = b[i];
	for(int i=1;i<=20;i++)
	{
		for(int j=1;j+(1<<i)-1 <= n;j++)
		{
			st[j][i] = max(st[j][i-1],st[j + (1<<(i-1))][i-1]);
		//	cout<<j<<" "<<i<<" "<<st[j][i]<<endl;
		}
		
	}

	/*
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)cout<<i<<" "<<j<<" "<<findmax(i,j)<<endl;
	}*/
	for(int i=1;i<=n;i++)
	{
		int l = 1;
		int r = i-1;
		int left = 0;
		int right = n+1;
		while(l<=r)
		{
			int mid = (l+r)>>1;
			//cout<<l<<" "<<r<<" "<<findmax(mid,i-1)<<endl;
			if(findmax(mid,i-1) >= b[i] + D)
			{
				left = mid;
				l = mid + 1;
			}
			else r = mid - 1;
		}
		leftD[i] = left;
		l = i+1;
		r = n;
		while(l <= r)
		{
			int mid = (l+r)>>1;
			if(findmax(i+1,mid) >= b[i] + D)
			{
				right = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		rightD[i] = right;
	}
	//cout<<endl;
	//for(int i=1;i<=n;i++)cout<<leftD[i]<<" "<<rightD[i]<<endl;
	int ans = 0;
	for(int now=1;now<=n;now++)
	{
		int i = aa[now].second;
		if(i < L || i > R)continue;
	//	cout<<i<<" ";
		//if(leftD[i] < L || rightD[i] > R)continue;
		if(ask(leftD[i],i) <= 0 && ask(i,rightD[i]) <= 0)
		{
	//		cout<<i<<endl;
			change(i,1);
			ans++;
		}
	}
 	return ans;
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i=0;i<H.size();i++)
      |              ~^~~~~~~~~

• 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