# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
47459 | Talant | Worst Reporter 3 (JOI18_worst_reporter3) | C++17 | 2082 ms | 10748 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>
#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long
using namespace std;
const int inf = (int)1e18 + 7;
const int N = (int)6e5 + 7;
int n,q,d[N],a[N];
int t,L,R;
int cnt;
bool check (int x) {
int o = floor(t / a[x]) * a[x] - x;
if (L <= o)
return true;
return false;
}
bool f(int x) {
int o = floor(t / a[x]) * a[x] - x;
if (R >= o)
return true;
return false;
}
main () {
scanf ("%lld%lld", &n,&q);
for (int i = 1; i <= n; i ++)
scanf ("%lld", &d[i]);
for (int i = 1; i <= n; i ++) {
if (i == 1)
a[i] = d[i];
else {
int l = 1,r = inf;
while (r - l > 1) {
int m = (r + l) >> 1;
int o = floor(m / a[i - 1]) * a[i - 1] - (i - 1);
if (o >= d[i] + 1 + (-i))
r = m;
else
l = m;
}
int o = floor(l / a[i - 1]) * a[i - 1] - (i - 1);
if (o >= d[i] + 1 + (-i))
r = l;
a[i] = r;
}
}
while (q --) {
scanf ("%lld%lld%lld", &t,&L,&R);
if (t < L) {
puts("0");
continue;
}
int l = 1,r = n;
while (r - l > 1) {
int m = (r + l) >> 1;
if (check(m))
l = m;
else
r = m;
}
if (check(r))
l = r;
if (!check(l))
l = 0;
if (l == 0 && t <= R) {
puts("1");
continue;
}
if (l == 0) {
puts("0");
continue;
}
int lo = 1,hi = l;
while (hi - lo > 1) {
int m = (hi + lo) >> 1;
if (f(m))
hi = m;
else
lo = m;
}
if (!f(hi)) {
puts("0");
continue;
}
if (f(lo))
hi = lo;
if (L <= t && t <= R)
printf("%lld\n", l - hi + 2);
else
printf("%lld\n", l - hi + 1);
}
}
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... |