Submission #817816

#	Time	Username	Problem	Language	Result	Execution time	Memory
817816		Alan	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	495 ms	25560 KiB

worst_reporter3

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

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<int> a {1}, idx {0};
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		a.push_back(x);
		a[i] = max(a[i-1], a[i]);
		a[i] = (a[i]-1) / a[i-1] * a[i-1] + a[i-1];
		idx.push_back(i);
	}
	reverse(idx.begin(), idx.end());
	while (q--) {
		int t, l, r;
		cin >> t >> l >> r;
		auto itl = lower_bound(idx.begin(), idx.end(), l, [&] (int x, int id) {return -x + t / a[x] * a[x] < id;});
		auto itr = upper_bound(idx.begin(), idx.end(), r, [&] (int id, int x) {return id < -x + t / a[x] * a[x];});
		cout << itr - itl << '\n';
	}
	return 0;
}

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