Submission #1252109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252109		LucaLucaM	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	339 ms	11196 KiB

worst_reporter3

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const ll INF = 1e10;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
 
  int n, q;
  std::cin >> n >> q;

  std::vector<ll> time(n + 1, 0);
  std::vector<ll> len(n + 1, 0);

  int d1;
  std::cin >> d1;
  time[1] = d1;
  len[1] = d1;

  for (int i = 2; i <= n; i++) {
    int d;
    std::cin >> d;
    ll k = (d + len[i - 1] - 1) / len[i - 1];
    time[i] = std::min(+INF, (ll) time[i - 1] * k);
    len[i] = std::min(+INF, len[i - 1] * k);
  }

  auto getPos = [&](int i, int t) -> ll {
    if (time[i] == +INF) {
      return -i;
    }
    if (len[i] == +INF) {
      return +INF;
    }
    return -i + (ll) len[i] * ((ll) t / time[i]);
  };

  auto query = [&](int p, int t) {
    if (getPos(n, t) > p) {
      return 0;
    }
    int l = 1, r = n;
    while (l < r) {
      int mid = (l + r) / 2;
      if (getPos(mid, t) <= p) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return n - r + 1;
  };

  while (q--) {
    int t, l, r;
    std::cin >> t >> l >> r;
    int answer = 0;
    if (l <= t && t <= r) {
      answer++;
    }
    answer += query(r, t);
    answer -= query(l - 1, t);
    std::cout << answer << '\n';
  }
  
  return 0;
}

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