結果

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

ソースコード

diff # 

/*
(q,),*e=[[*map(int,s.split())]for s in open(0)]
def spf(n):
 spf=[*range(n+1)]
 for i in range(2,n+1):
  for j in range(i*2,n+1,i):
   spf[j]=i
 return spf
s=spf(10**6)
for i in range(10**6+1):
  if s[i]==i:
    s[i]=0

#https://tjkendev.github.io/procon-library/python/range_query/merge-sort-tree.html
from bisect import bisect
from heapq import merge

# count elements A_i s.t. A_i <= k for i in [l, r)
def query1(N0, data, l, r, k):
    L = l + N0; R = r + N0
    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s += bisect(data[R-1], k-1)
        if L & 1:
            s += bisect(data[L-1], k-1)
            L += 1
        L >>= 1; R >>= 1
    return s

N=len(s)
A=s[:]
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
for i, a in enumerate(A):
    data[N0-1+i] = [a]
for i in range(N, N0):
    data[N0-1+i] = []
for i in range(N0-2, -1, -1):
    *data[i], = merge(data[2*i+1], data[2*i+2])
for l,r in e:
  if l==1:
    ans=1
  else:
    ans=query1(N0,data,l,r+1,l)
  print(ans)
*/

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

vector<int> spf(int n) {
  vector<int> spf(n+1);
  iota(spf.begin(), spf.end(), 0);
  for (int i = 2; i <= n; ++i) {
    for (int j = i*2; j <= n; j += i) {
      spf[j] = i;
    }
  }
  return spf;
}

int query1(int N0, vector<vector<int>> &data, int l, int r, int k) {
  int L = l + N0, R = r + N0;
  int s = 0;
  while (L < R) {
    if (R & 1) {
      --R;
      s += upper_bound(data[R-1].begin(), data[R-1].end(), k-1) - data[R-1].begin();
    }
    if (L & 1) {
      s += upper_bound(data[L-1].begin(), data[L-1].end(), k-1) - data[L-1].begin();
      ++L;
    }
    L >>= 1;
    R >>= 1;
  }
  return s;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int q;
  cin >> q;
  vector<pair<int,int>> e(q);
  for (int i = 0; i < q; ++i) {
    cin >> e[i].first >> e[i].second;
  }

  int MAX = 1e6;
  vector<int> s = spf(MAX);
  for (int i = 0; i <= MAX; ++i) {
    if (s[i] == i) s[i] = 0;
  }

  int N = s.size();
  int N0 = 1;
  while (N0 < N) N0 <<= 1;
  vector<vector<int>> data(2*N0);

  for (int i = 0; i < N; ++i) {
    data[N0-1+i] = {s[i]};
  }
  for (int i = N; i < N0; ++i) {
    data[N0-1+i] = {};
  }
  for (int i = N0-2; i >= 0; --i) {
    vector<int> &left = data[2*i+1], &right = data[2*i+2];
    data[i].resize(left.size() + right.size());
    merge(left.begin(), left.end(), right.begin(), right.end(), data[i].begin());
  }

  for (auto [l, r] : e) {
    int ans;
    if (l == 1) {
      ans = 1;
    } else {
      ans = query1(N0, data, l, r+1, l);
    }
    cout << ans << '\n';
  }
}
0