oj.uz

Submission #642917

# Submission time Handle Problem Language Result Execution time Memory
642917 2022-09-20T19:04:18 Z valerikk Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 663 ms 23192 KB 
#include <cstdio>

#define MAXN 500005
#define MAXT 1000000001
#define MAXK 65

int N, Q;
int D[MAXN];
int W[MAXN], C[MAXN], S[MAXN];
int Z[MAXK], K;

int count(int T, int L) {
  if (T < L)
    return 0;

  for (int i = 0, t = T; i < K; ++i) {
    S[i] = t % C[Z[i]] * W[Z[i]];
    t /= C[Z[i]];
  }

  int low = 0, high = N + 1;
  while (high - low > 1) {
    int mid = (low + high) / 2;

    int X = T - mid;
    for (int i = 0; i < K && Z[i] <= mid; ++i) {
      X -= S[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

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d%d", &N, &Q);
      |   ~~~~~^~~~~~~~~~~~~~~~
worst_reporter3.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d", &D[i]);
      |     ~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d%d%d", &T, &L, &R);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 9540 KB Output is correct
2 Correct 303 ms 9216 KB Output is correct
3 Correct 356 ms 9204 KB Output is correct
4 Correct 311 ms 9196 KB Output is correct
5 Correct 310 ms 9268 KB Output is correct
6 Correct 326 ms 9292 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 9540 KB Output is correct
2 Correct 303 ms 9216 KB Output is correct
3 Correct 356 ms 9204 KB Output is correct
4 Correct 311 ms 9196 KB Output is correct
5 Correct 310 ms 9268 KB Output is correct
6 Correct 326 ms 9292 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 341 ms 8944 KB Output is correct
14 Correct 327 ms 7188 KB Output is correct
15 Correct 309 ms 8620 KB Output is correct
16 Correct 329 ms 8576 KB Output is correct
17 Correct 614 ms 8540 KB Output is correct
18 Correct 611 ms 8580 KB Output is correct
19 Correct 613 ms 8488 KB Output is correct
20 Correct 614 ms 8568 KB Output is correct
21 Correct 585 ms 8596 KB Output is correct
22 Correct 594 ms 8664 KB Output is correct
23 Correct 592 ms 8568 KB Output is correct
24 Correct 608 ms 8568 KB Output is correct
25 Correct 324 ms 10408 KB Output is correct
26 Correct 338 ms 10196 KB Output is correct
27 Correct 568 ms 9032 KB Output is correct
28 Correct 663 ms 8908 KB Output is correct
29 Correct 651 ms 8932 KB Output is correct
30 Correct 630 ms 8928 KB Output is correct
31 Correct 642 ms 8900 KB Output is correct
32 Correct 333 ms 23192 KB Output is correct
33 Correct 1 ms 212 KB Output is correct