Submission #253028

#	Time	Username	Problem	Language	Result	Execution time	Memory
253028		wwdd	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	650 ms	29692 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
vl w,x;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int n,q;
	cin >> n >> q;
	for(int i=0;i<n;i++) {
		ll t;
		cin >> t;
		w.push_back(t);
	}
	ll pm = 1;
	x.push_back(pm);
	for(int i=0;i<n;i++) {
		pm = (w[i]+pm-1)/pm*pm;
		x.push_back(pm);
	}
	while(q--) {
		ll ti,l,r;
		cin >> ti >> l >> r;
		ll st = 0,ed = x.size()-1;
		ll la = -1;
		while(st <= ed) {
			ll m = (st+ed)/2;
			ll po = (ti/x[m]*x[m])-m;
			if(po >= l) {
				la = m;
				st = m+1;
			} else {
				ed = m-1;
			}
		}
		st = 0;ed = x.size()-1;
		ll lb = -1;
		while(st <= ed) {
			ll m = (st+ed)/2;
			ll po = (ti/x[m]*x[m])-m;
			if(po > r) {
				lb = m;
				st = m+1;
			} else {
				ed = m-1;
			}
		}
		cout << la-lb << '\n';
	}
}

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