This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// oooo
/*
har chi delet mikhad bebar ~
gitar o ba khodet nabar! ~
;Amoo_Hasan;
*/
#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long double ld;
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define endl '\n'
constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;
int a[N], d[N];
int T[N], L[N], R[N];
map<int, pair<int, int> > s;
int main() {
ios :: sync_with_stdio(0), cin.tie(0);
int n, q; cin >>n >>q;
for(int i = 1; i <= n; i++) cin >>a[i];
d[1] = a[1];
for(int i = 2; i <= n; i++) {
if(a[i] <= a[i - 1]) {
d[i] = d[i - 1];
continue;
}
ll cnt = a[i] / d[i - 1];
if(cnt * d[i - 1] < a[i]) cnt++;
d[i] = d[i - 1] * cnt;
}
vector<int> vc;
for(int i = 1; i <= n;) {
if(d[i] > 1e9) continue;
int ptr = i;
while(ptr <= n && d[ptr] == d[i]) ptr++;
s[d[i]] = make_pair(i, ptr - 1);
vc.push_back(d[i]);
i = ptr;
}
sort(All(vc)), vc.erase(unique(All(vc)), vc.end());
if(Sz(vc) >= 40) assert(0);
for(int j = 0; j < q; j++) {
cin >>T[j] >>L[j] >>R[j];
int ans = 0;
for(auto i : vc) {
if(i > T[j]) break;
int cnt = (T[j] / i) * i;
int l = cnt + -s[i].second, r = cnt + -s[i].first;
if(r < L[j] || l > R[j]) continue;
if(r >= R[j] && l <= L[j]) {
ans += R[j] - L[j] + 1;
continue;
}
if(R[j] >= r && L[j] <= l) {
ans += r - l + 1;
continue;
}
if(r <= R[j]) ans += r - L[j] + 1;
else ans += R[j] - l + 1;
}
cout<<ans + (T[j] >= L[j] && T[j] <= R[j]) <<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... |