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 <iostream>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long llo;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
llo n,q;
llo aa;
cin>>n>>q;
vector<llo> bb;
bb.pb(1);
for(llo i=0;i<n;i++){
cin>>aa;
llo cc=bb[bb.size()-1];
llo dd=(aa/cc)*cc;
if(aa%cc>0){
dd+=cc;
}
bb.pb(dd);
// cout<<dd<<" ";
}
// cout<<endl;
llo tt,l,r;
while(q--){
cin>>tt>>l>>r;
if(tt<l){
cout<<0<<endl;
continue;
}
llo ma=tt-tt%bb[bb.size()-1]-(bb.size());
if(ma>r){
cout<<0<<endl;
continue;
}
llo low=0;
llo high=bb.size()-1;
while(low<high-1){
llo mid=(low+high)/2;
llo val=tt-tt%bb[mid]-mid;
if(val<l){
high=mid;
}
else{
low=mid;
}
}
llo ind2;
llo val2=tt-tt%bb[high]-high;
//cout<<low<<" "<<high<<" "<<val2<<endl;
if(val2<l){
ind2=low;
}
else{
ind2=high;
}
low=0;
high=bb.size()-1;
while(low<high-1){
llo mid=(low+high)/2;
llo val=tt-tt%bb[mid]-mid;
if(val>r){
low=mid;
}
else{
high=mid;
}
}
llo ind3;
llo val3=tt-tt%bb[low]-low;
if(val3>r){
ind3=high;
}
else{
ind3=low;
}
// cout<<ind3<<" "<<ind2<<endl;
cout<<ind2-ind3+1<<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... |