oj.uz

Submission #201872

# Submission time Handle Problem Language Result Execution time Memory
201872 2020-02-12T15:46:25 Z EntityIT Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 649 ms 21752 KB 
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  int n, q; cin >> n >> q;
  vector<int> d(n);
  for (int i = 0; i < n; ++i) cin >> d[i];

  vector<int> f(n); f[0] = d[0];
  for (int i = 1; i < sz(f); ++i) f[i] = (int)min( (LL)2e9, (LL)( (d[i] + f[i - 1] - 1) / f[i - 1]) * f[i - 1]);

  while (q--) {
    int t, l, r; cin >> t >> l >> r;

    int ans = (l <= t && t <= r);

    int L = 0, R = n;
    while (L < R) {
      int M = (L + R) >> 1;
      if (t - t % f[M] - (M + 1) <= r) R = M;
      else L = M + 1;
    }

    ans += -L;

    L = 0; R = n;
    while (L < R) {
      int M = (L + R) >> 1;
      if (t - t % f[M] - (M + 1) < l) R = M;
      else L = M + 1;
    }

    ans += L;

    cout << ans << '\n';
  }

  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 21704 KB Output is correct
2 Correct 647 ms 21688 KB Output is correct
3 Correct 628 ms 21752 KB Output is correct
4 Correct 649 ms 21628 KB Output is correct
5 Correct 619 ms 21624 KB Output is correct
6 Correct 649 ms 21752 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 21704 KB Output is correct
2 Correct 647 ms 21688 KB Output is correct
3 Correct 628 ms 21752 KB Output is correct
4 Correct 649 ms 21628 KB Output is correct
5 Correct 619 ms 21624 KB Output is correct
6 Correct 649 ms 21752 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 6 ms 376 KB Output is correct
13 Runtime error 87 ms 13352 KB Execution killed with signal 8 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -