Submission #201873

#	Time	Username	Problem	Language	Result	Execution time	Memory
201873		EntityIT	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	647 ms	21880 KiB

worst_reporter3

#include<bits/stdc++.h>

using namespace std;

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

const int inf = 1e9 + 1;
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)inf, (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 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81