/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int n, q;
ll d[N];
ll get(ll l1, ll r1, ll l, ll r){
return max(0ll, min(r1 + 1, r + 1) - max(l1, l));
}
void solve(){
cin >> n >> q;
for(int i = 1; i <= n; ++i){
cin >> d[i];
}
vector<array<ll, 3>> C;
C.pb({1, 1, d[1]});
for(int i = 2; i <= n; ++i){
if(d[i] <= C.back()[2]){
C.back()[1]++;
}else{
ll x = C.back()[2];
x = (d[i] + x-1) / x * x;
C.pb({i, i, x});
}
}
// for(auto [l, r, D]: C) cout << l << ' ' << r << ' ' << D << '\n';
for(int i = 1; i <= q; ++i){
ll t, l, r; cin >> t >> l >> r;
ll ans = 0;
for(int j = 0; j < C.size(); ++j){
ll pos = -C[j][1] + (t/C[j][2] * C[j][2]);
ans += get(pos, pos + C[j][1] - C[j][0], l, r);
}
cout << ans + (l <= t && t <= r) << '\n';
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |