This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 5e5 + 9;
const ll mod = 1e9 + 7;
const ll base = 31;
typedef pair<ll,ll> LL;
ll n,Q,x,pre[N],T,L,R,a[N],val[N];
ll Getpos(ll nTime,ll id){
if (!id) return nTime;
//cout<<nTime<<" "<<id <<" "<< val[id]<<"x\n";
ll jump = nTime/(val[id]); //cout<<jump; exit(0);
return jump * val[id] - id;
}
ll GetLast(){
ll l,m,h; l = 0; h = n;
while(l <= h){
m = (l + h)/2; //cout<<Getpos(T,m)<<"x\n";
if (Getpos(T,m) >= L) l = m + 1;
else h = m - 1;
}
//exit(0);
return h;
}
ll GetFirst(){
ll l,m,h; l = 0; h = n;
while(l <= h){
m = (l + h)/2;
if (Getpos(T,m) > R) l = m + 1;
else h = m - 1;
}
return l;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "tst"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
}
cin>>n>>Q;
for (ll i = 1;i <= n;i++) cin>>x,pre[i] = (pre[i - 1] + x),a[i] = x;
val[1] = a[1];
for (ll i = 2;i <= n;i++){
ll up = ceil((ld)a[i]/val[i - 1]);
val[i] = val[i - 1]*up;
}
//cout<<Getpos(190,5); return 0;
while(Q--){
cin>>T>>L>>R;
//for (ll i = 0;i <= n;i++) cout<<Getpos(T,i)<<" "; return 0;
if (T < L) cout<<"0\n";
else cout<<GetLast() - GetFirst() + 1<<"\n";
//cout<<GetLast()<<" "<<GetFirst(); return 0;
}
}
Compilation message (stderr)
worst_reporter3.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization "O2"
|
worst_reporter3.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |