oj.uz

Submission #1057623

# Submission time Handle Problem Language Result Execution time Memory
1057623 2024-08-14T01:45:44 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 3846 ms 436976 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 1e5 + 5;
const ll oo = 1e9;
const int lg = 17;
const int M = 1e7;
const ll mod = 1e9 + 7;
#define pii pair<int, int>
#define fi first
#define se second
#define NAME "maxsub"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, a[nmax], m;

int r[nmax];
int es1[M + 5];
vector<int> c;

int get(int u){
    return r[u] ? r[u] = get(r[u]) : u;
}

struct hs{
    int x, y, w;
};
int R[nmax];
pii get(int l, int r){
    if(R[l] <= r) return {l, R[l]};
    return {l, -1};
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen(NAME".inp", "r", stdin);
//    freopen(NAME".out", "w", stdout);
    cin >> n;
    int ma = 0;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        ma = max(ma, a[i]);
        c.push_back(a[i]);
    }
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    n = c.size();
    for(int i = 1; i <= n; ++i) a[i] = c[i - 1];
    int p1 = 1;
    for(int i = 1; i <= M + 1; ++i){
        while(p1 <= n && a[p1] < i) ++p1;
        es1[i] = p1;
    }
    vector<hs> v;
    pii tmp;
    ll ans = 0, base = 1;
    while(1){
        int i, u, j;
        for(i = n; i >= 1; --i){
            R[i] = i + 1;
            while(R[i] <= n && get(R[i]) == get(i)) R[i] = R[R[i]];
        }
        for(u = 1, i; u <= n; ++u){
            i = a[u];
            for(j = 1; j <= M / i; ++j){
                int l = max(i + 1, j * i), r = min(M, (j + 1) * i - 1);
                l = es1[l], r = es1[r + 1] - 1;
                if(l <= r){
                    tmp = get(l, r);
                    if(get(tmp.fi) != get(u)) v.push_back({u, tmp.fi, a[tmp.fi] % a[u]});
                    else if(tmp.se != -1) v.push_back({u, tmp.se, a[tmp.se] % a[u]});
                }
            }
        }
        sort(v.begin(), v.end(), [](hs a, hs b){
             return a.w < b.w;
             });
        for(auto [x, y, w] : v){
//            cout << x << ' ' << y << ' ' << w << "\n";
            int u = get(x);
            int v = get(y);
            if(u != v){
                r[u] = v;
//                cout << a[x] << ' ' << a[y] << "\n";
                ans += w;
            }
        }
        bool ok = 1;
        for(int i = 2; i <= n; ++i){
            if(get(i) != get(i - 1)) ok = 0;
        }
        if(ok)break;
        v.clear();
    }
    cout << ans;
}
/*
4
3
5
9
11
*/

Compilation message

sirni.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main(){
      | ^~~~
sirni.cpp: In function 'int main()':
sirni.cpp:67:21: warning: right operand of comma operator has no effect [-Wunused-value]
   67 |         for(u = 1, i; u <= n; ++u){
      |                     ^
sirni.cpp:60:17: warning: unused variable 'base' [-Wunused-variable]
   60 |     ll ans = 0, base = 1;
      |                 ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39772 KB Output is correct
2 Correct 47 ms 42932 KB Output is correct
3 Correct 15 ms 40280 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 39904 KB Output is correct
2 Correct 157 ms 40936 KB Output is correct
3 Correct 16 ms 40028 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39984 KB Output is correct
2 Correct 14 ms 39692 KB Output is correct
3 Correct 15 ms 39984 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 55104 KB Output is correct
2 Correct 575 ms 91692 KB Output is correct
3 Correct 232 ms 66264 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 44536 KB Output is correct
2 Correct 339 ms 91944 KB Output is correct
3 Correct 210 ms 54844 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 92212 KB Output is correct
2 Correct 739 ms 141424 KB Output is correct
3 Correct 243 ms 66520 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 48448 KB Output is correct
2 Correct 728 ms 140080 KB Output is correct
3 Correct 203 ms 66872 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 67132 KB Output is correct
2 Correct 2698 ms 436168 KB Output is correct
3 Correct 208 ms 66880 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 67644 KB Output is correct
2 Correct 3846 ms 436500 KB Output is correct
3 Correct 239 ms 67136 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 44292 KB Output is correct
2 Correct 3772 ms 436976 KB Output is correct
3 Correct 266 ms 68412 KB Output is correct