# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
154251 | karma | Worst Reporter 3 (JOI18_worst_reporter3) | C++14 | 624 ms | 23464 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 Task "test"
#define ll long long
#define pb emplace_back
using namespace std;
const int N = int(5e5) + 5;
int n, q, a[N], t, l, r, low, high, mid, ans;
bool Check(int x, bool type) {
int pos = (t / a[x]) * a[x] - x - 1;
if(type) return pos <= r;
return pos >= l;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if(fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
}
cin >> n >> q;
for(int i = 0; i < n; ++i) {
cin >> a[i];
if(i) a[i] = ((a[i] - 1) / a[i - 1] + 1) * a[i - 1];
}
while(q --) {
cin >> t >> l >> r;
if(t >= l && t <= r) ans = 1;
else ans = 0;
low = 0, high = n - 1;
while(low <= high) {
mid = (low + high) >> 1;
if(Check(mid, 0)) low = mid + 1;
else high = mid - 1;
}
if(high < 0) {cout << ans << "\n"; continue;}
ans += low, low = 0, high = n - 1;
while(low <= high) {
mid = (low + high) >> 1;
if(Check(mid, 1)) high = mid - 1;
else low = mid + 1;
}
cout << ans - low << '\n';
}
}
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... |