Submission #1157375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157375		fryingduc	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	284 ms	15204 KiB

worst_reporter3

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 5e5 + 5;
const int inf = 1e9;
int n, d[maxn], q;
int qt[maxn], ql[maxn], qr[maxn], ord[maxn];
int res[maxn];

int cdiv(int x, int y) {
  return (x + y - 1) / y;
}

int calc(int x, int y, int u, int v) {
  if (y < u || x > v) return 0;
  return max(0, min(y, v) - max(x, u) + 1);
}

void solve() {
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> d[i];
  }
  for (int i = 2; i <= n; ++i) {
    if (inf / cdiv(d[i], d[i - 1]) < d[i - 1]) {
      for (int j = i; j <= n; ++j) {
        d[j] = inf + 1;
      }
      break;
    }
    d[i] = cdiv(d[i], d[i - 1]) * d[i - 1];
  }
  vector<array<int, 3>> itv;
  for (int i = 1; i <= n; ++i) {
    if (d[i] > inf) {
      break;
    }
    int cur = 0;
    while (i + cur <= n and d[i] == d[i + cur]) ++cur;
    itv.push_back({-(i + cur - 1), -i, d[i]});
    i = i + cur - 1;
  }
  for (int i = 1; i <= q; ++i) {
    cin >> qt[i] >> ql[i] >> qr[i];
    ord[i] = i;
  }
  sort(ord + 1, ord + q + 1, [](const int &x, const int &y) -> bool {
    return qt[x] < qt[y];
  });
  for (int p = 1; p <= q; ++p) {
    int cur = 0, x = qt[ord[p]];
    while (p + cur <= q and x == qt[ord[p + cur]]) ++cur;
    int prv = x;
    for (auto &[l, r, a]:itv) {
      int c = (prv - r - 1) / a;
      l += a * c, r += a * c;
      prv = l;
    }
    for (int i = p; i < p + cur; ++i) {
      res[ord[i]] = (ql[ord[i]] <= x and x <= qr[ord[i]]);
      for (auto [l, r, a]:itv) {
        res[ord[i]] += calc(l, r, ql[ord[i]], qr[ord[i]]);
      }
//      debug(x, ql[ord[i]], qr[ord[i]], res[ord[i]]);
    }
//    debug(x, itv);
    p = p + cur - 1;
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << '\n';
  }
}

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

  solve();

  return 0;
}

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