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 optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef stack<ll> sll;
typedef queue<ll> qll;
typedef deque<ll> dll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
// #define endl '\n'
#define pb push_back
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define BACK(i,a,b) for(int i = a; i >= b; i--)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define bp __builtin_popcountll
#define gcd __gcd
#define bit(i,n) ((n>>i)&1)
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
const int MAXN = (5e5)+5;
// const ll SQRT = 4;
const long long inf = 1e18;
const long long MOD = 1e9+7;
ll n,q,s[MAXN],d[MAXN],f[MAXN];
signed main()
{
fastIO
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
cin>>n>>q;
FOR(i,1,n) cin>>d[i];
f[0]=1;
FOR(i,1,n) f[i]=int((d[i]+f[i-1]-1)/f[i-1])*f[i-1];
while(q--)
{
int t,l,r,up,m;
cin>>t>>l>>r;
if(t<l) {cout<<0<<endl; continue;}
int lx=0,rx=n+1;
while(lx<rx-1)
{
m=lx+rx>>1;
if(-m+(t/f[m])*f[m]<l) rx=m;
else lx=m;
}
up=lx;
lx=-1,rx=n;
while(lx<rx-1)
{
m=lx+rx>>1;
if(-m+(t/f[m])*f[m]>r) lx=m;
else rx=m;
}
cout<<up-m+1<<endl;
}
}
Compilation message (stderr)
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:53:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | m=lx+rx>>1;
| ~~^~~
worst_reporter3.cpp:61:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | m=lx+rx>>1;
| ~~^~~
worst_reporter3.cpp:65:11: warning: 'm' may be used uninitialized in this function [-Wmaybe-uninitialized]
65 | cout<<up-m+1<<endl;
| ~~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |