Submission #220650

#	Time	Username	Problem	Language	Result	Execution time	Memory
220650		rama_pang	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	724 ms	9592 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, Q;
  scanf("%d %d", &N, &Q);

  vector<int> D(N + 1, 1);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &D[i]);
  }

  // Compute the array X, which means the i-th person will move X[i] units every X[i] seconds
  vector<long long> X(N + 1, 1);
  for (int i = 1; i <= N; i++) {
    X[i] = ((D[i] + X[i - 1] - 1) / X[i - 1]) * X[i - 1];
  }

  auto Query = [&](int T, int L, int R) { // Count T - R - i <= T mod X[i] <= T - L - i
    int res = N + 1;

    { // Count how many i where T mod X[i] < T - R - i holds, and decrease it from answer.
      // T mod X[i] is monotonically increasing, so we can binary search for it.
      int lo = -1, hi = N;
      while (lo < hi) {
        int mid = (lo + hi + 1) >> 1;
        if (T % X[mid] < T - R - mid) {
          lo = mid;
        } else {
          hi = mid - 1;
        }
      }

      res -= lo + 1; // there are lo+1 such elements which T mod X[i] < T - R - i holds. (i = [0, N])
    }

    { // Count how many i where T mod X[i] > T - L - i holds, and decrease it from answer.
      // T mod X[i] is monotonically increasing, so we can binary search for it.
      int lo = 0, hi = N + 1;
      while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (T % X[mid] > T - L - mid) {
          hi = mid;
        } else {
          lo = mid + 1;
        }
      }

      res -= (N - lo) + 1; // there are N - lo + 1 such elements which T mod X[i] > T - L - i holds. (i = [0, N])
    }

    return res;
  };

  for (int qi = 0; qi < Q; qi++) {
    int T, L, R;
    scanf("%d %d %d", &T, &L, &R);
    printf("%d\n", Query(T, L, R));
  }

  return 0;
}

Compilation message (stderr)

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

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81