結果
問題 | No.3101 Range Eratosthenes Query |
ユーザー |
![]() |
提出日時 | 2025-04-11 22:29:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 985 ms / 3,000 ms |
コード長 | 2,929 bytes |
コンパイル時間 | 3,845 ms |
コンパイル使用メモリ | 283,088 KB |
実行使用メモリ | 263,744 KB |
最終ジャッジ日時 | 2025-04-11 22:29:43 |
合計ジャッジ時間 | 21,879 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define REP(i,n) for(ll i=0;i<(ll)(n);i++) #define ALL(x) (x).begin(),(x).end() #define IO ios::sync_with_stdio(false),cin.tie(nullptr); #define LB(v,x) (int)(lower_bound(ALL(v),x)-(v).begin()) #define UQ(v) sort(ALL(v)), erase(unique(ALL(v)),v.end()) template<typename T> bool chmax(T&a, const T&b){ if(a<b){ a=b; return true; } return false; } template<typename T> bool chmin(T&a, const T&b){ if(b<a){ a=b; return true; } return false; } template<typename T> using rpriority_queue=priority_queue<T,vector<T>,greater<T>>; using ll=long long; const int INF=1e9+10; const ll INFL=4e18; using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>; using VS=vector<string>; using PL=pair<ll,ll>; using VP=vector<PL>; using TL=tuple<ll,ll,ll>; using WG=vector<vector<pair<int,ll>>>; /// @file mst.hpp /// @brief マージソート木 template<typename T> struct MergeSortTree{ MergeSortTree()=default; /// @brief 配列 v からマージソート木を構築する MergeSortTree(const vector<T>&v){ n=v.size(); mx=*max_element(v.begin(),v.end()),mn=*min_element(v.begin(),v.end()); dat=vector<vector<T>>(n<<1); for(int i=0;i<n;i++)dat[n+i]={v[i]}; for(int i=n-1;i>0;i--){ merge( dat[i<<1].begin(),dat[i<<1].end(), dat[i<<1|1].begin(),dat[i<<1|1].end(), back_inserter(dat[i])); } } /// @brief 区間 [l, r) に存在する val 未満の値の個数を返す /// @note O(log(N)^2) int count_lt(int l,int r,T val){ l+=n,r+=n; int ret=0; while(l<r){ if(l&1)ret+=search(l++,val); if(r&1)ret+=search(--r,val); l>>=1,r>>=1; } return ret; } /// @brief 区間 [l, r) に存在する val 以下の値の個数を返す /// @note O(log(N)^2) int count_le(int l,int r,T val){return count_lt(l,r,val+1);} /// @brief 区間 [l, r) に存在する val より大きい値の個数を返す /// @note O(log(N)^2) int count_gt(int l,int r,T val){return n-l-count_le(l,r,val);} /// @brief 区間 [l, r) に存在する val 以上の値の個数を返す /// @note O(log(N)^2) int count_ge(int l,int r,T val){return n-l-count_lt(l,r,val);} /// @brief 区間 [l, r) の小さい方から k 番目の値を返す /// @brief k は 1-indexed で与える /// @note O(log(N)^3) T kth(int l,int r,int k){ T lo=mn-1,hi=mx+1; while(hi-lo>1){ T mid=(hi+lo)/2; (count_lt(l,r,mid)>=k?hi:lo)=mid; } return lo; } private: int n; vector<vector<T>>dat; int search(int i,T val){return lower_bound(dat[i].begin(),dat[i].end(),val)-dat[i].begin();} T mx,mn; }; int main(){ IO; const int mx=1e6+10; VL md(mx,1); for(ll i=2;i<mx;i++){ if(md[i]==1){ for(ll j=i*2;j<mx;j+=i) chmax(md[j],j/i); } } //[L,R)の中でL以上の数の個数 MergeSortTree<ll>mst(md); int Q;cin>>Q; while(Q--){ int l,r;cin>>l>>r;r++; if(l==1) cout<<1<<'\n'; else cout<<mst.count_lt(l,r,l)<<'\n'; } }