結果

問題 No.3101 Range Eratosthenes Query
ユーザー noya2
提出日時 2025-04-08 02:50:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,271 bytes
コンパイル時間 3,818 ms
コンパイル使用メモリ 290,392 KB
実行使用メモリ 30,776 KB
最終ジャッジ日時 2025-04-08 02:50:59
合計ジャッジ時間 12,498 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

// TLE

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

const int mx = 1001001;

void solve(){
    int q; cin >> q;
    vector<vector<pair<int,int>>> rs(mx);
    for (int i = 0; i < q; i++){
        int l, r; cin >> l >> r;
        rs[l].emplace_back(r,i);
    }
    vector<int> ans(q);
    for (auto [r, i] : rs[1]){
        ans[i] = 1;
    }
    vector<bool> ex(mx,true);
    vector<int> buf(mx);
    int bid = 0;
    for (int l = 2; l < mx; l++){
        if (rs[l].empty()) continue;
        ranges::sort(rs[l]);
        int cnt = 0;
        int ir = l;
        for (auto [r, i] : rs[l]){
            while (ir <= r){
                if (ex[ir]){
                    cnt++;
                    buf[bid++] = ir;
                    for (int x = ir*2; x < mx; x += ir){
                        ex[x] = false;
                    }
                }
                ir++;
            }
            ans[i] = cnt;
        }
        while (bid > 0){
            int p = buf[--bid];
            for (int x = p*2; x < mx; x += p){
                ex[x] = true;
            }
        }
    }
    for (int i = 0; i < q; i++){
        cout << ans[i] << '\n';
    }
}

int main(){
    int t = 1;
    // std::cin >> t;
    while (t--){
        solve();
    }
}
0