Submission #1176255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176255		rafsanamin2020	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	312 ms	11236 KiB

worst_reporter3

#include <bits/stdc++.h>

typedef long long int ll;

using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n, q, sum = 1;
  cin >> n >> q;
  vector<ll> d(n + 1);
  vector<ll> pd(n + 1);

  d[0] = pd[0] = 1;
  for (ll i = 1; i <= n; i++)
  {
    cin >> d[i];
    sum = ((d[i] / sum) + (d[i] % sum == 0 ? 0 : 1)) * sum;
    pd[i] = sum;
  }
  for (ll i = 0; i < q; i++)
  {
    ll t, l, r;
    cin >> t >> l >> r;

    ll lo = -n, hi = 1, x, y, al, ar;

    while (lo < hi)
    {
      x = ((lo + hi) / 2) - (((lo + hi >= 0) || (abs((lo + hi)) % 2 == 0)) ? 0 : 1);
      y = x + ((t / pd[-x]) * pd[-x]);
      // cout << " " << lo << " " << hi << " " << x << " " << y << "\n";

      if (y >= l)
      {
        hi = x;
      }
      else
      {
        lo = x + 1;
      }

      al = (lo + hi) / 2;
    }

    lo = -n, hi = 1;

    while (lo < hi)
    {
      x = ((lo + hi) / 2) - (((lo + hi >= 0) || (abs((lo + hi)) % 2 == 0)) ? 0 : 1);

      y = x + ((t / pd[-x]) * pd[-x]);
      // cout << " " << lo << " " << hi << " " << x << " " << y << "\n";

      if (y <= r)
      {
        lo = x + 1;
      }
      else
      {
        hi = x;
      };

      ar = (lo + hi) / 2;
    }
    // if (lx < 1 || rx < 1)
    // {
    //   cout << "0\n";
    // }
    cout << ar - al << "\n";
  }
}

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