Submission #438695

#	Time	Username	Problem	Language	Result	Execution time	Memory
438695		peijar	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	824 ms	33092 KiB

worst_reporter3

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 2e9;

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbPersonnes, nbRequetes;
  cin >> nbPersonnes >> nbRequetes;

  vector<int> lenteurs(nbPersonnes + 1);
  for (int iPersonne = 1; iPersonne <= nbPersonnes; ++iPersonne)
    cin >> lenteurs[iPersonne];

  vector<int> frequency(nbPersonnes + 1), delta(nbPersonnes + 1);
  frequency[0] = 1, delta[0] = 1;

  for (int iPersonne = 1; iPersonne <= nbPersonnes; ++iPersonne) {
    int nbFois =
        (lenteurs[iPersonne] + delta[iPersonne - 1] - 1) / delta[iPersonne - 1];
    frequency[iPersonne] = nbFois * frequency[iPersonne - 1];
    if (frequency[iPersonne] > INF) {
      frequency[iPersonne] = delta[iPersonne] = INF;

      continue;
    }
    delta[iPersonne] = delta[iPersonne - 1] * nbFois;
  }

  auto calcPos = [&](int iPer, int curT) {
    int nbFois = curT / frequency[iPer];
    return -iPer + nbFois * delta[iPer];
  };

  auto calcLess = [&](int bound, int curT) -> int {
    if (calcPos(nbPersonnes, curT) >= bound)
      return 0;
    int lo = 0, up = nbPersonnes;
    while (lo < up) {
      int mid = (lo + up) / 2;
      if (calcPos(mid, curT) < bound)
        up = mid;
      else
        lo = mid + 1;
    };
    return nbPersonnes - lo + 1;
  };

  for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
    int temps, deb, fin;
    cin >> temps >> deb >> fin;
    /*int ret = 0;
    for (int iPer = 0; iPer <= nbPersonnes; ++iPer) {
      int pos = calcPos(iPer, temps);
      if (pos >= deb and pos <= fin)
        ret++;
    }
    cout << ret << '\n';*/
    cout << calcLess(fin + 1, temps) - calcLess(deb, temps) << '\n';
  }
}

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