Submission #320030

#	Time	Username	Problem	Language	Result	Execution time	Memory
320030		NachoLibre	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	647 ms	25572 KiB

worst_reporter3

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

const int N = 500005;
int n, q, t, l, r;
long long x[N] = {1};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		cin >> x[i];
		x[i] = x[i - 1] * ((x[i] - 1) / x[i - 1] + 1);
	}
	for(int qi = 1; qi <= q; ++qi) {
		cin >> t >> l >> r;
		int sl = 0, sr = n;
		if(x[0] * (t / x[0]) < l) sl = sr = -1;
		while(sl < sr) {
			int sm = (sl + sr + 1) / 2;
			if(x[sm] * (t / x[sm]) - sm >= l) {
				sl = sm;
			} else {
				sr = sm - 1;
			}
		}
		int wl = sl;
		sl = 0, sr = n;
		if(x[n] * (t / x[n]) - n > r) sl = sr = n + 1;
		while(sl < sr) {
			int sm = (sl + sr) / 2;
			if(x[sm] * (t / x[sm]) - sm <= r) {
				sr = sm;
			} else {
				sl = sm + 1;
			}
		}
		cout << max(0, wl - sl + 1) << "\n";
	}
	return 0;
}

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