#include<bits/stdc++.h>
using namespace std;
#define task "reporter3"
#define lb lower_bound
#define ub upper_bound
#define ALL(v) (v).begin(),(v).end()
#define zs(v) ll((v).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=(a),_b=(b);i<=_b;++i)
#define per(i,b,a) for(ll i=(b),_a=(a);i>=_a;--i)
#define rep_(i,a,b) for(ll i=(a),_b=(b);i<_b;++i)
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const ll d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
const ll mod=1000000007; /// 998244353
const ll base=311;
const ll N=5e5+5;
ll n,q,a[N];
ll b[N];
void biot()
{
cin>>n>>q;
for(ll i=1;i<=n;++i) cin>>a[i];
b[0]=1;
for(ll i=1;i<=n;++i)
{
b[i]=((a[i]+b[i-1]-1)/b[i-1])*b[i-1];
// cout<<b[i]<<' ';
}
// cout<<endl;
while(q--)
{
ll L,R,t;
cin>>t>>L>>R;
ll l=0, r=n;
ll ansl=-1, ansr=-1;
while(l<=r)
{
ll mid=(l+r)>>1;
if((t/b[mid])*b[mid]-mid>=L) l=mid+1, ansl=mid;
else r=mid-1;
}
// for(ll i=1;i<=n;++i) cout<<t/b[i]*b[i]-i<<' ';
// cout<<endl;
l=0, r=n;
while(l<=r)
{
ll mid=(l+r)>>1;
if(t/b[mid]*b[mid]-mid<=R) r=mid-1, ansr=mid;
else l=mid+1;
}
// cout<<ansr<<endl;
if(ansr==-1||ansl==-1) cout<<0<<'\n';
else cout<<ansl-ansr+1<<'\n';
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
biot();
}
Compilation message
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
69 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
worst_reporter3.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
70 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
633 ms |
11412 KB |
Output is correct |
2 |
Correct |
644 ms |
22008 KB |
Output is correct |
3 |
Correct |
620 ms |
22108 KB |
Output is correct |
4 |
Correct |
638 ms |
22112 KB |
Output is correct |
5 |
Correct |
631 ms |
22408 KB |
Output is correct |
6 |
Correct |
647 ms |
22008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
633 ms |
11412 KB |
Output is correct |
2 |
Correct |
644 ms |
22008 KB |
Output is correct |
3 |
Correct |
620 ms |
22108 KB |
Output is correct |
4 |
Correct |
638 ms |
22112 KB |
Output is correct |
5 |
Correct |
631 ms |
22408 KB |
Output is correct |
6 |
Correct |
647 ms |
22008 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
361 ms |
19800 KB |
Output is correct |
14 |
Correct |
371 ms |
15864 KB |
Output is correct |
15 |
Correct |
355 ms |
20088 KB |
Output is correct |
16 |
Correct |
379 ms |
19832 KB |
Output is correct |
17 |
Correct |
479 ms |
11128 KB |
Output is correct |
18 |
Correct |
474 ms |
11128 KB |
Output is correct |
19 |
Correct |
445 ms |
11152 KB |
Output is correct |
20 |
Correct |
454 ms |
11100 KB |
Output is correct |
21 |
Correct |
442 ms |
11128 KB |
Output is correct |
22 |
Correct |
443 ms |
10976 KB |
Output is correct |
23 |
Correct |
444 ms |
11000 KB |
Output is correct |
24 |
Correct |
443 ms |
11000 KB |
Output is correct |
25 |
Correct |
612 ms |
22008 KB |
Output is correct |
26 |
Correct |
633 ms |
21996 KB |
Output is correct |
27 |
Correct |
496 ms |
11488 KB |
Output is correct |
28 |
Correct |
492 ms |
11444 KB |
Output is correct |
29 |
Correct |
493 ms |
11340 KB |
Output is correct |
30 |
Correct |
530 ms |
11384 KB |
Output is correct |
31 |
Correct |
533 ms |
11384 KB |
Output is correct |
32 |
Correct |
472 ms |
21624 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |