結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー PNJ
提出日時 2025-04-11 22:37:16
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 712 ms / 3,000 ms
コード長 2,983 bytes
コンパイル時間 3,452 ms
コンパイル使用メモリ 292,192 KB
実行使用メモリ 60,192 KB
最終ジャッジ日時 2025-04-11 22:37:36
合計ジャッジ時間 17,604 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

template <class T>
struct segtree{
  // segtree<T> seg(n, op, e);
  int size = 1, n;
  T (*op)(T, T);
  T e;
  vector<T> seg;

  segtree(int n, T(*op)(T, T), T e) : n(n), op(op), e(e) {
    while (size < n) size <<= 1;
    seg.resize(2 * size, e);
  }

  void set(int i, T x) {
    i += size;
    seg[i] = x;
    while (i >>= 1) { seg[i] = op(seg[2 * i], seg[2 * i + 1]); }
  }

  T get(int i) { return seg[i + size]; }

  void add(int i, T x) { set(i, get(i) + x); }
  
  void set_array(vector<T> A) {
    assert (size >= int(A.size()));
    for (int i = 0; i < int(A.size()); i++) set(i, A[i]);
  }

  T prod(int l, int r) {
    T L = e, R = e;
    l += size, r += size;
    while (l < r) {
      if (l & 1) L = op(L, seg[l]), l += 1;
      if (r & 1) R = op(seg[r -= 1], R);
      l >>= 1, r >>= 1;
    }
    return op(L, R);
  }

  T all_prod() { return seg[1]; }

  // [l, r)でtrueとなるやつ
  int max_right(int l, function<bool(T)> check) {
    assert (0 <= l && l <= n);
    assert (check(e) == true);
    if (l == n) return n;
    l += size;
    T sm = e;
    while (1) {
      while (l % 2 == 0) l >>= 1;
      if (!check(op(sm, seg[l]))) {
        while (l < size) {
          l <<= 1;
          if (check(op(sm, seg[l])))  sm = op(sm, seg[l]), l += 1;
        }
        return l - size;
      }
      sm = op(sm, seg[l]), l += 1;
      if ((l & -l) == l) break;
    }
    return n;
  }

  int min_left(int r, function<bool(T)> check) {
    assert (0 <= r && r <= n);
    assert (check(e) == true);
    if (r == 0) return 0;
    r += size;
    T sm = e;
    while (1) {
      r -= 1;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!check(op(sm, seg[r]))) {
        while (r < size) {
          r <<= 1;
          r += 1;
          if (check(op(sm, seg[r]))) {
            sm = op(sm, seg[r]), r -= 1;
          }
        }
        return r + 1 - size;
      }
      sm = op(sm, seg[r]);
      if ((r & -r) == r) break;
    }
    return 0;
  }
};

template <class T>
T add(T x, T y) { return x + y; }

int main() {
  int N = 1000000;
  vector<int> D(N + 1, 1);
  D[0] = 0, D[1] = 0;
  for (int i = 1; i <= N; i++) {
    for (int d = 2; d <= N; d++) {
      if (i * d > N) break;
      D[i * d] = max(D[i * d], i);
    }
  }
  vector<vector<int>> G(N + 1);
  for (int d = 2; d <= N; d++) {
    G[D[d]].push_back(d);
  }
  segtree seg(N + 1, add, 0);
  for (int i = 1; i <= N; i++) seg.set(i, 1);

  int Q;
  cin >> Q;
  vector<tuple<int, int, int>> query;
  for (int i = 0; i < Q; i++) {
    int L, R;
    cin >> L >> R;
    query.push_back({L, R, i});
  }
  sort(query.begin(), query.end());

  int L = N + 1;
  vector<int> ans(Q, 0);
  while (query.size()) {
    auto q = query.back();
    query.pop_back();
    auto [l, r, j] = q;
    for (int i = l; i < L; i++) {
      for (auto d : G[i]) seg.set(d, 0);
    }
    L = l;
    ans[j] = seg.prod(l, r + 1);
  }
  for (auto res : ans) {
    cout << res << endl;
  }
}
0