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 target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 500001;
int n, q;
int arr[mxN];
int main()
{
//freopen("filename.in", "r", stdin);
//freopen("filename.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin>>n>>q;
owo(i, 1, n+1) {
cin>>arr[i];
}
arr[0] = 1;
owo(i, 1, n+1) {
if(arr[i-1]>=1000000001) arr[i] = 1000000001;
else {
arr[i] = arr[i-1]*((arr[i]+arr[i-1]-1)/arr[i-1]);
}
}
int t, left, right;
while(q--) {
cin>>t>>left>>right;
int pos = t;
if(pos<left) {
cout<<"0\n";
continue;
}
pos= t/arr[n]*arr[n]-n;
if(pos>right) {
cout<<"0\n";
continue;
}
int first = 0;
int second = 0;
int l = 0;
int r = n;
while(l<r) {
int mid = (l+r+1)/2;
//cout<<mid<<" "<<(-mid+t/arr[mid]*arr[mid])<<"\n";
if(-mid+t/arr[mid]*arr[mid]>=left) {
l = mid;
}else {
r=mid-1;
}
}
first = l;
l = 0;
r = n;
while(l<r) {
int mid = (l+r)/2;
if(-mid+t/arr[mid]*arr[mid]<=right)r = mid;
else l = mid+1;
}
if(l>first) {
cout<<"0\n";
}else {
cout<<(first-l+1)<<"\n";
}
}
return 0;
}
Compilation message (stderr)
worst_reporter3.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("O3")
worst_reporter3.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:53:13: warning: unused variable 'second' [-Wunused-variable]
int second = 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... |