Submission #220649

#	Time	Username	Problem	Language	Result	Execution time	Memory
220649		rama_pang	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	19 / 100	646 ms	8440 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
const int INF = 1.5e9;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, Q;
  cin >> N >> Q;

  vector<int> D(N + 1, 1);
  for (int i = 1; i <= N; i++) {
    cin >> D[i];
  }

  // Compute the array X, which means the i-th person will move X[i] units every X[i] seconds
  vector<int> X(N + 1, 1);
  for (int i = 1; i <= N; i++) {
    X[i] = (int) min((long long) INF, 1ll * ((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;
    cin >> T >> L >> R;
    cout << Query(T, L, R) << "\n";
  }

  return 0;
}

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