Submission #156159

#	Time	Username	Problem	Language	Result	Execution time	Memory
156159		luciocf	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	709 ms	25584 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5+10;

int n;

int d[maxn];
int tempo[maxn];

int busca1(int t, int pos)
{
	int ini = 0, fim = n, ans = -1;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		if ((t/tempo[mid])*tempo[mid] - mid >= pos) ans = mid, ini = mid+1;
		else fim = mid-1;
	}

	return ans;
}

int busca2(int t, int pos)
{
	int ini = 0, fim = n, ans = n+1;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		if ((t/tempo[mid])*tempo[mid] - mid <= pos) ans = mid, fim = mid-1;
		else ini = mid+1;
	}

	return ans;
}

int main(void)
{
	int q;
	scanf("%d %d", &n, &q);

	for (int i = 1; i <= n; i++)
		scanf("%d", &d[i]);

	tempo[0] = 1, tempo[1] = d[1];
	for (int i = 2; i <= n; i++)
	{
		int x = d[i]/tempo[i-1];

		if (d[i]%tempo[i-1] != 0) x++;

		tempo[i] = x*tempo[i-1];
	}

	for (int i = 1; i <= q; i++)
	{
		int t, l, r;
		scanf("%d %d %d", &t, &l, &r);

		int R = busca2(t, r);
		int L = busca1(t, l);

		if (R > L) printf("0\n");
		else printf("%d\n", L-R+1);
	}
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d[i]);
   ~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &t, &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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