Submission #1057623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057623		vjudge1	Sirni (COCI17_sirni)	C++17	140 / 140	3846 ms	436976 KiB

sirni

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14