# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
774883 | Antonn_114 | Worst Reporter 3 (JOI18_worst_reporter3) | C++14 | 501 ms | 13404 KiB |
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 <bits/stdc++.h>
using namespace std;
// Write down the limits of the problem here
int main() {
// Try to avoid cin, cout :)
int tc = 1; // scanf("%d", &tc);
while(tc--) {
/// Your solution here
int n, q;
scanf("%d%d", &n, &q);
vector<int> d(n + 1);
for (int i = 1; i <= n ; i++) scanf("%d", &d[i]);
vector<int> f(n + 1);
f[0] = 1;
d[0] = 1;
for (int i = 1; i <= n; i++){
f[i] = int(ceil(d[i]/double(f[i - 1])))*f[i - 1];
}
while(q--){
int t, l, r;
scanf("%d%d%d", &t, &l, &r);
int L = 0;
int R = n;
while(L <= R){
int m = (L + R) >> 1;
int T = (t/f[m])*f[m] - m;
if (T < l) R = m - 1;
else L = m + 1;
}
int firstpos = L;
L = 0, R = n;
while( L <= R){
int m = (L + R )>> 1;
int T = (t/f[m])*f[m] - m;
if (T > r) L = m + 1;
else R = m - 1;
}
int lastpos = R;
printf("%d\n", max(0, firstpos - lastpos - 1));
}
}
return 0;
}
/*
* Ermm don't underestimate Div2A, pls...
*
* IMPORTANT:: If there isn't a clear-cut approach for your program, DO NOT CODE YET!
*
* Analyze the time complexity and space complexity even if it *seems* efficient
*
* Write down some notes for more complicated problems
*
* Also, please, CP isn't supposed to be complicated
*
**/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |