Submission #1126026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126026		codexistent	Sirni (COCI17_sirni)	C++20	140 / 140	2851 ms	535788 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define MAXN 100005
#define MAXL 10000005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)

ll n, r = 0, p[MAXN], sz[MAXN];
vector<ll> v;
vector<pair<ll, ll>> e[MAXL];

void compress(){
    set<ll> s(begin(v), end(v));
    v.assign(begin(s), end(s));
}

ll find(ll x){
    return (x == p[x]) ? x : (p[x] = find(p[x]));  
}

bool onion(ll a, ll b){
    a = find(a), b= find(b);
    if(a == b) return false;

    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    p[a] = p[b] = a;
    return true;
}

int main(){
    cin >> n;
    FOR(i, 1, n) {
        ll x; cin >> x;
        v.push_back(x);
    }
    compress();

    n = v.size();
    FOR(i, 1, n - 1) e[v[i] % v[i - 1]].push_back({i - 1, i});
    FOR(i, 0, n - 1){
        for(ll j = v[i]; j <= MAXL; ){
            ll lo = i + 1, hi = n;
            while(lo < hi){
                ll md = (lo + hi) / 2;
                if(md == n || j <= v[md]){
                    hi = md;
                }else{
                    lo = md + 1;
                }
            }
            if(hi == n) break;
            e[v[lo] % v[i]].push_back({lo, i});
            j = v[lo] / v[i] * v[i] + v[i];
        }
    }
    FOR(i, 0, n - 1) p[i] = i, sz[i] = 1;
    FOR(i, 0, MAXL - 1) for(pair<ll, ll> ei : e[i]) r += onion(ei.first, ei.second) * i;
    cout << r << endl;
}

• 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