Submission #49532

#	Time	Username	Problem	Language	Result	Execution time	Memory
49532		MatheusLealV	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	1037 ms	262144 KiB

worst_reporter3

#include <bits/stdc++.h>
#define N 500050
using namespace std;

int n, q, D[N], F[N], g[N];

int upper_bound(int t, int T)
{
	int ini = 0, fim = n, mid, best = n + 1;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(g[mid] * (t/g[mid]) - mid <= T)
		{
			best = mid;

			fim = mid - 1;
		}

		else ini = mid + 1;
	}

	return best;
}

int lower_bound(int t, int T)
{
	int ini = 0, fim = n, mid, best = n + 1;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(g[mid] * (t/g[mid]) - mid < T)
		{
			best = mid;

			fim = mid - 1;
		}

		else ini = mid + 1;
	}

	return best;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>q;

	D[0] = 1, g[0] = 1;

	for(int i = 1; i <= n; i++)
	{
		cin>>D[i];

		g[i] = g[i - 1] * ceil((double)D[i]/(double) g[i - 1]);
	}

	for(int i = 1, T, A, B ; i <= q; i++)
	{
		cin>>T>>A>>B;

		cout<<abs(upper_bound(T, B) - lower_bound(T, A))<<"\n";
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81