結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー umezo
提出日時 2025-04-12 04:45:24
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 620 ms / 3,000 ms
コード長 1,248 bytes
コンパイル時間 4,025 ms
コンパイル使用メモリ 288,272 KB
実行使用メモリ 15,932 KB
最終ジャッジ日時 2025-04-12 04:45:47
合計ジャッジ時間 21,030 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
template <class T> using V=vector<T>;
template <class T> using VV=V<V<T>>;

template<typename T>
struct BIT{
private:
  vector<T> A;
  const int n;
  
public:
  BIT(int _n) : A(_n+1,0), n(_n){}
  T sum(int i){
    T s=0;
    while(i>0){
      s+=A[i];
      i-=i&-i;
    }
    return s;
  }
  
  T sum(int i,int j){
    return sum(j)-sum(i-1);
  }
  void add(int i,T x){
    while(i<=n){
      A[i]+=x;
      i+=i&-i;
    }
  }
  void update(int i,T x){
    T tmp=sum(i,i);
    if(tmp!=x) add(i,x-tmp);
  }
};
 
int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  BIT<ll> bit(1000000);
  
  int q;
  cin>>q;
  V<int> L(q),R(q);
  rep(i,q) cin>>L[i]>>R[i];
  V<pair<int,int>> P(q);
  rep(i,q) P[i]={L[i],i};
  sort(ALL(P));
  stack<int> st;
  rep(i,q){
    int j=P[i].second;
    st.push(j);
  }
  
  V<int> ANS(q);
  for(int i=1000000;i>=1;i--){
    bit.add(i,1);
    for(int j=i*2;j<=1000000;j+=i) bit.update(j,0);
    while(st.size() && L[st.top()]==i){
      auto j=st.top(); st.pop();
      ANS[j]=bit.sum(L[j],R[j]);
    }
  }
  rep(i,q) cout<<ANS[i]<<"\n";
    
  return 0;
}
0