Submission #734884

#	Time	Username	Problem	Language	Result	Execution time	Memory
734884		lukameladze	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	570 ms	29356 KiB

worst_reporter3

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
 #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 5e5 + 5;
int t,n,a[N], q, per[N], d[N];
int get_pos(int x, int tm) {
	return (tm / per[x]) * per[x] - x;
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for (int i = 1; i <= n; i++) {
		cin>>d[i];
	}
	per[0] = 1; per[1] = d[1];
	for (int i = 2; i <= n; i++) {
		per[i] = (d[i] + per[i - 1] - 1) / per[i - 1] * per[i - 1];
	}
	while (q--) {
		int t, l, r;
		cin>>t>>l>>r;
		int le = 0, ri = n, ans = -1, ans1 = n + 1;
		while (le <= ri) {
			int mid = (le + ri) / 2;
			if (get_pos(mid, t) >= l) {
				ans = mid;
				le = mid + 1;
			} else ri = mid - 1;
		}
		le = 0, ri = n;
		while (le <= ri) {
			int mid = (le + ri) / 2;
			if (get_pos(mid, t) <= r) {
				ans1 = mid; ri = mid - 1;
			} else le = mid + 1;
		}
		cout<<max(ans - ans1 + 1, 0LL)<<"\n";
	}
}

Compilation message (stderr)

worst_reporter3.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main() {
      | ^~~~

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