Submission #963778

#	Time	Username	Problem	Language	Result	Execution time	Memory
963778		abczz	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	1469 ms	33172 KiB

worst_reporter3

#include <iostream>
#define ll long long

using namespace std;

ll n, q, t, ql, qr, l, r, ul, ur, mid, A[500001], D[500001], T[500001];
int main() {
  cin >> n >> q;
  for (int i=1; i<=n; ++i) cin >> A[i];
  T[0] = D[0] = 1;
  for (int i=1; i<=n; ++i) {
    T[i] = T[i-1] * (ll)((A[i]+D[i-1]-1)/D[i-1]);
    D[i] = (ll)((A[i]+D[i-1]-1)/D[i-1]) * D[i-1];
  }
  while (q--) {
    cin >> t >> ql >> qr;
    l = 0, r = n;
    while (l < r) {
      mid = (l+r+1)/2;
      if (ql <= (ll)(t/T[mid]) * D[mid] - mid) l = mid;
      else r = mid-1;
    }
    ur = l;
    l = 0, r = n;
    while (l < r) {
      mid = (l+r)/2;
      if ((ll)(t/T[mid]) * D[mid] - mid <= qr) r = mid;
      else l = mid+1;
    }
    ul = l;
    if (ql <= (ll)(t/T[ur]) * D[ur] - ur && (ll)(t/T[ul]) * D[ul] - ul <= qr) cout << ur-ul+1 << '\n';
    else cout << "0\n";
  }
}

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