#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 5e5+5;
int n,q,d[N],hori[N];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> d[i];
hori[1] = d[1];
for(int i = 2; i <= n; i++) hori[i] = ((d[i]+hori[i-1]-1)/hori[i-1])*hori[i-1];
while(q--){
int l,r,t;
cin >> t >> l >> r;
int l1 = 0;
int r1 = n;
int l2 = 1e9;
int r2 = -1;
while(l1 <= r1){
int mid = (l1+r1)/2;
int kaori;
if(mid == 0) kaori = t;
else kaori = hori[mid]*(t/hori[mid])-mid;
if(kaori >= l){
r2 = mid;
l1 = mid+1;
}
else r1 = mid-1;
}
l1 = 0;
r1 = n;
while(l1 <= r1){
int mid = (l1+r1)/2;
int kaori;
if(mid == 0) kaori = t;
else kaori = hori[mid]*(t/hori[mid])-mid;
if(kaori <= r){
l2 = mid;
r1 = mid-1;
}
else l1 = mid+1;
}
//cout << l2 << " " << r2 << "\n";
if(r2 < l2) cout << 0 << "\n";
else cout << r2-l2+1 << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |