oj.uz

Submission #220649

# Submission time Handle Problem Language Result Execution time Memory
220649 2020-04-08T10:52:22 Z rama_pang Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 646 ms 8440 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 7520 KB Output is correct
2 Correct 622 ms 7344 KB Output is correct
3 Correct 646 ms 7404 KB Output is correct
4 Correct 603 ms 7416 KB Output is correct
5 Correct 598 ms 7328 KB Output is correct
6 Correct 606 ms 7264 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 7520 KB Output is correct
2 Correct 622 ms 7344 KB Output is correct
3 Correct 646 ms 7404 KB Output is correct
4 Correct 603 ms 7416 KB Output is correct
5 Correct 598 ms 7328 KB Output is correct
6 Correct 606 ms 7264 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Runtime error 78 ms 8440 KB Execution killed with signal 8 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -