結果
問題 | No.3101 Range Eratosthenes Query |
ユーザー |
|
提出日時 | 2025-04-11 22:01:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 194 ms / 3,000 ms |
コード長 | 4,935 bytes |
コンパイル時間 | 2,723 ms |
コンパイル使用メモリ | 205,260 KB |
実行使用メモリ | 18,580 KB |
最終ジャッジ日時 | 2025-04-11 22:01:24 |
合計ジャッジ時間 | 7,762 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; using SS = int; class SegmentTree{ public: int siz = -1,n = -1; vector<SS> dat; SS op(SS a, SS b){return a+b;} SS e(){return 0;} void renew (SS &a,SS x){ a = op(a,x); //a = x; //set(pos,x)で可能. //その他. } SegmentTree(int N){init(N);} SegmentTree(const vector<SS> &A){//長さ配列サイズに合わせる. siz = 1; n = A.size(); while(siz < n) siz *= 2; dat.resize(siz*2,e()); for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i); for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1)); } void init(int N){ //全要素単位元に初期化. siz = 1; n = N; while(siz < n) siz *= 2; dat.assign(siz*2,e()); } void init(const vector<SS> &A){//長さ配列サイズに合わせる. siz = 1; n = A.size(); dat.resize(siz*2,e()); for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i); for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1)); } void set(int pos,SS x){ pos = pos+siz; dat.at(pos) = x; while(pos != 1){ pos = pos/2; dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1)); } } void update(int pos,SS x){ pos = pos+siz; renew(dat.at(pos),x); while(pos != 1){ pos = pos/2; dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1)); } } SS findans(int l, int r){ SS retl = e(),retr = e(); l += siz,r += siz; while(l < r){ if(l&1) retl = op(retl,dat.at(l++)); if(r&1) retr = op(dat.at(--r),retr); l >>= 1; r >>= 1; } return op(retl,retr); } SS get(int pos){return dat.at(pos+siz);} SS rangeans(int l, int r){return findans(l,r);} SS allrange(){return dat.at(1);} //rightは) leftは[で 渡す&返す. int maxright(const function<bool(SS)> f,int l = 0){ //fを満たさない最小の箇所を返す なければn. l += siz; int r = n+siz; vector<int> ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okl = e(); for(int i=0; i<ls.size(); i++){ l = ls.at(i); SS now = op(okl,dat.at(l)); if(!f(now)){ while(l < siz){ l <<= 1; now = op(okl,dat.at(l)); if(f(now)){okl = now; l++;} } return l-siz; } okl = now; } for(int i=rs.size()-1; i>=0; i--){ l = rs.at(i); SS now = op(okl,dat.at(l)); if(!f(now)){ while(l < siz){ l <<= 1; now = op(okl,dat.at(l)); if(f(now)){okl = now; l++;} } return l-siz; } okl = now; } return n; } int minleft(const function<bool(SS)> f,int r = -1){ //fを満たす最小の箇所を返す なければ0. if(r == -1) r = n; int l = siz; r += siz; vector<int> ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okr = e(); for(int i=0; i<rs.size(); i++){ r = rs.at(i); SS now = op(dat.at(r),okr); if(!f(now)){ while(r < siz){ r <<= 1; r++; now = op(dat.at(r),okr); if(f(now)){okr = now; r--;} } return r+1-siz; } okr = now; } for(int i=ls.size()-1; i>=0; i--){ r = ls.at(i); SS now = op(dat.at(r),okr); if(!f(now)){ while(r < siz){ r <<= 1; r++; now = op(dat.at(r),okr); if(f(now)){okr = now; r--;} } return r+1-siz; } okr = now; } return 0; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int Q; cin >> Q; vector<tuple<int,int,int>> LR(Q); int idx = 0; for(auto &[l,r,p] : LR) cin >> l >> r,p = idx++; sort(LR.begin(),LR.end(),[&](auto &a,auto &b){return get<1>(a) < get<1>(b);}); vector<int> D(1001001); for(int i=1; i<1001001; i++) for(int k=i+i; k<1001001; k+=i) D.at(k) = i; SegmentTree Z(1001001); int R = 0; vector<int> answer(Q); for(auto [l,r,anspos] : LR){ while(R < r) Z.update(D.at(++R),1); answer.at(anspos) = r-l+1-Z.rangeans(l,r+1); } for(auto a : answer) cout << a << "\n"; }