This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define SZ(x) ll(x.size())
const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;
int n , q , D[MAXN];
vector<int> vec;
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> q; D[0] = 1;
for(int i = 1 ; i <= n ; i++){
cin >> D[i];
}
vec.push_back(0);
for(int i = 1 ; i <= n ; i++){
D[i] = (D[i] + D[i - 1] - 1) / D[i - 1] * D[i - 1];
if(D[i] != D[vec.back()]){
vec.push_back(i);
}
if(D[i] > MOD) break;
}
vec.push_back(n + 1);
while(q--){
int t , l , r , ans = 0;
cin >> t >> l >> r;
for(int i = 0 ; i + 1 < SZ(vec) ; i++){
int T = t / D[vec[i]];
int L = T * D[vec[i]] - vec[i + 1] + 1 , R = T * D[vec[i]] - vec[i];
L = max(L , l); R = min(R , r);
ans += max(0 , R - L + 1);
}
cout << ans << endl;
}
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... |