Submission #284775

#	Time	Username	Problem	Language	Result	Execution time	Memory
284775		ChrisT	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	870 ms	29432 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
const int MN = 5e5 + 5;
long long speed[MN], d[MN];
int main () {
	int n,q;
	scanf ("%d %d",&n,&q);
	for (int i = 1; i <= n; i++) scanf ("%lld",&d[i]);
	speed[0] = d[0] = 1;
	for (int i = 1; i <= n; i++) {
		speed[i] = speed[i-1] * ((d[i] + d[i-1] - 1) / d[i-1]);
		d[i] = d[i-1] * speed[i] / speed[i-1];
	}
	auto bs = [&] (int t, int x) { //at time t, what is first one <= x
		int low = 0, high = n, mid, ans = n+1;
		while (low <= high) {
			mid = (low + high) / 2;
			long long pos = -mid + t / speed[mid] * d[mid];
			if (pos <= x) high = (ans = mid) - 1;
			else low = mid + 1;
		}
		return ans;
	}; 
	while (q--) {
		int t,l,r;
		scanf ("%d %d %d",&t,&l,&r);
		printf ("%d\n",bs(t,l-1)-bs(t,r));
	} 
	return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:7:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 |  scanf ("%d %d",&n,&q);
      |  ~~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:8:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |  for (int i = 1; i <= n; i++) scanf ("%lld",&d[i]);
      |                               ~~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   scanf ("%d %d %d",&t,&l,&r);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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