# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
642916 | valerikk | Worst Reporter 3 (JOI18_worst_reporter3) | C++17 | 2050 ms | 27332 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 <cstdio>
#define MAXN 500005
#define MAXT 1000000001
#define MAXK 65
int N, Q;
int D[MAXN];
int W[MAXN], C[MAXN];
int Z[MAXK], K;
int count(int T, int L) {
if (T < L)
return 0;
int low = 0, high = N + 1;
while (high - low > 1) {
int mid = (low + high) / 2;
int X = T - mid;
for (int i = 0, t = T; i < K && Z[i] <= mid; ++i) {
int r = t % C[Z[i]];
t /= C[Z[i]];
X -= r * W[Z[i]];
}
if (X >= L)
low = mid;
else
high = mid;
}
return low + 1;
}
int main() {
scanf("%d%d", &N, &Q);
for (int i = 1; i <= N; ++i) {
scanf("%d", &D[i]);
}
W[1] = 1;
C[1] = D[1];
for (int i = 2; i <= N; ++i) {
if (MAXT / C[i - 1] < W[i - 1])
W[i] = MAXT;
else
W[i] = C[i - 1] * W[i - 1];
C[i] = (D[i] + W[i] - 1) / W[i];
if (C[i] > MAXT)
C[i] = MAXT;
}
for (int i = 1; i <= N; ++i) {
if (C[i] != 1)
Z[K++] = i;
}
while (Q--) {
int T, L, R;
scanf("%d%d%d", &T, &L, &R);
printf("%d\n", count(T, L) - count(T, R + 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... |