QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#260255#7749. A Simple MST ProblemjccccTL 549ms46112kbC++174.8kb2023-11-21 23:02:322023-11-21 23:02:33

Judging History

你现在查看的是最新测评结果

  • [2023-11-21 23:02:33]
  • 评测
  • 测评结果:TL
  • 用时:549ms
  • 内存:46112kb
  • [2023-11-21 23:02:32]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
int vis[N];
vector<int> pri;

void init(int n){
    vis[1] = 1;
    for(int i = 2; i <= N - 10; i++){
        if(!vis[i]) vis[i] = i, pri.push_back(i);
        for(int j = 0; i * pri[j] <= N - 10 && j < pri.size(); j++){
            vis[i * pri[j]] = pri[j];
            if(i % pri[j] == 0) break;
        }
    }
}

int ne_l, ne_r, sz, down, up;

void cal_l(int u, int sum, vector<int>& ob){
    if(u == sz){
        if(sum >= down && (ne_l == down - 1 || ne_l <= sum)){
            ne_l = sum;
        }
        return ;
    }
    for(int i = 1; i <= 21; i++){
        cal_l(u + 1, sum, ob);
        if(ll(sum) * ob[u] >= up) break;
        sum = sum * ob[u];
    }
}

void cal_r(int u, int sum, vector<int>& ob){
    if(u == sz){
        if(sum > down && (ne_r == up + 1 || ne_r >= sum)){
            ne_r = sum;
        }
        return ;
    }
    for(int i = 1; i <= 21; i++){
        cal_r(u + 1, sum, ob);
        if(ll(sum) * ob[u] > up) break;
        sum = sum * ob[u];
    }
}

void cpSort(std::vector<std::array<int, 3>> &a) {
    int M = 0;
    for (const auto &[x, y, w] : a)
        M = std::max(M, w);
    std::vector<std::vector<int>> Ton(M + 1);
    for (int i = 0; i < a.size(); i++) {
        Ton[a[i][2]].push_back(i);
    }
    std::vector<std::array<int, 3>> b;
    for (int x = 0; x <= M; x++) {
        for (auto i : Ton[x])
            b.push_back(a[i]);
    }
    a = b;
}

void solve(){
    int l, r; cin >> l >> r;
    if(l == r){
        cout << 0 << '\n'; return ;
    }
    if(r - l + 1 <= 200){
        set<int> st[r - l + 2];
        for(int i = l; i <= r; i++){
            int num = i, lst = 0;
            while(num != 1){
                if(lst != vis[num]) st[i - l + 1].insert(vis[num]), lst = vis[num];
                num = num / vis[num];
            }
            //cout << i << ' ' << st[i - l + 1].size() << '\n';
        }
        vector<array<ll, 3>> e;
        for(int i = l; i <= r; i++){
            for(int j = i + 1; j <= r; j++){
                int idx = 0;
                for(auto it : st[i - l + 1]){
                    if(st[j - l + 1].find(it) != st[j - l + 1].end()){
                        idx += 1;
                    }
                }
                int cnt = st[i - l + 1].size() + st[j - l + 1].size() - idx;
                e.push_back({i - l + 1, j - l + 1, cnt});
                e.push_back({j - l + 1, i - l + 1, cnt});
            }
        }
        sort(e.begin(), e.end(), [&](array<ll, 3> a, array<ll, 3> b){
            return a[2] < b[2];
        });
        vector<int> p(r - l + 2);
        for(int i = 1; i <= r - l + 1; i++) p[i] = i;
        function<int(int)> find = [&] (int x){
            if(p[x] != x) return p[x] = find(p[x]);
            return p[x];
        };
        ll ans = 0;
        for(auto [u, v, w] : e){
            int pa = find(u), pb = find(v);
            if(pa == pb) continue;
            p[pa] = pb;
            ans += w;
        }
        cout << ans << '\n';
    }
    else {
        int idx = 0;
        for(int i = l; i <= r; i++){
            if(vis[i] == i){
                idx = i; break;
            }
        }
        vector<array<int, 3>> e;
        for (int i = l; i <= r; i++) {
            int num = i, lst = 0;
            vector<int> ob;
            while (num != 1) {
                if(lst != vis[num]) ob.push_back(vis[num]), lst = vis[num];
                num = num / vis[num];
            }
            ne_l = l - 1, ne_r = r + 1, sz = ob.size();
            down = l, up = i;
            cal_l(0, 1, ob);
            down = i, up = r;
            cal_r(0, 1, ob);
            if(ne_l >= l){
                e.push_back({ne_l - l + 1, i - l + 1, sz});
            }
            if(ne_r <= r){
                e.push_back({i - l + 1, ne_r - l + 1, sz});
            }
            if(i != idx) e.push_back({i - l + 1, idx - l + 1, sz + (i % idx != 0)});
        }
        cpSort(e);
        vector<int> p(r - l + 2);
        for(int i = 1; i <= r - l + 1; i++) p[i] = i;
        function<int(int)> find = [&] (int x){
            if(p[x] != x) return p[x] = find(p[x]);
            return p[x];
        };
        ll ans = 0;
        for(auto [u, v, w] : e){
            int pa = find(u), pb = find(v);
            if(pa == pb) continue;
            p[pa] = pb;
            ans += w;
        }
        cout << ans << '\n';
    }
}

int main(){
    init(N);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0 - 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 7924kb

input:

5
1 1
4 5
1 4
1 9
19 810

output:

0
2
3
9
1812

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 98ms
memory: 15384kb

input:

2
27 30
183704 252609

output:

8
223092

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 98ms
memory: 15828kb

input:

1
183704 252609

output:

223092

result:

ok single line: '223092'

Test #4:

score: 0
Accepted
time: 549ms
memory: 37760kb

input:

2
639898 942309
30927 34660

output:

983228
11512

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 509ms
memory: 46112kb

input:

3
21731 33468
46192 370315
1712 3753

output:

34608
948775
5299

result:

ok 3 lines

Test #6:

score: 0
Accepted
time: 173ms
memory: 17360kb

input:

4
15237 67700
10918 86104
98287 116980
17432 23592

output:

148811
210927
60893
18687

result:

ok 4 lines

Test #7:

score: -100
Time Limit Exceeded

input:

5
5594 70302
19202 69588
5634 7877
59821 469300
97439 261121

output:

179735
145706
6565
1203684
488669

result: