#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
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;
^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
623 ms |
20892 KB |
Output is correct |
2 |
Correct |
608 ms |
20748 KB |
Output is correct |
3 |
Correct |
625 ms |
20848 KB |
Output is correct |
4 |
Correct |
618 ms |
20836 KB |
Output is correct |
5 |
Correct |
607 ms |
20856 KB |
Output is correct |
6 |
Correct |
607 ms |
20728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
623 ms |
20892 KB |
Output is correct |
2 |
Correct |
608 ms |
20748 KB |
Output is correct |
3 |
Correct |
625 ms |
20848 KB |
Output is correct |
4 |
Correct |
618 ms |
20836 KB |
Output is correct |
5 |
Correct |
607 ms |
20856 KB |
Output is correct |
6 |
Correct |
607 ms |
20728 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
398 ms |
19320 KB |
Output is correct |
14 |
Correct |
428 ms |
19832 KB |
Output is correct |
15 |
Correct |
396 ms |
18680 KB |
Output is correct |
16 |
Correct |
402 ms |
19064 KB |
Output is correct |
17 |
Correct |
495 ms |
23288 KB |
Output is correct |
18 |
Correct |
524 ms |
23292 KB |
Output is correct |
19 |
Correct |
483 ms |
23416 KB |
Output is correct |
20 |
Correct |
509 ms |
23288 KB |
Output is correct |
21 |
Correct |
487 ms |
23288 KB |
Output is correct |
22 |
Correct |
500 ms |
23416 KB |
Output is correct |
23 |
Correct |
489 ms |
23288 KB |
Output is correct |
24 |
Correct |
494 ms |
23416 KB |
Output is correct |
25 |
Correct |
617 ms |
20728 KB |
Output is correct |
26 |
Correct |
600 ms |
20984 KB |
Output is correct |
27 |
Correct |
522 ms |
22900 KB |
Output is correct |
28 |
Correct |
552 ms |
23136 KB |
Output is correct |
29 |
Correct |
523 ms |
22772 KB |
Output is correct |
30 |
Correct |
532 ms |
22904 KB |
Output is correct |
31 |
Correct |
554 ms |
23284 KB |
Output is correct |
32 |
Correct |
485 ms |
19448 KB |
Output is correct |
33 |
Correct |
5 ms |
384 KB |
Output is correct |