oj.uz

Submission #482815

# Submission time Handle Problem Language Result Execution time Memory
482815 2021-10-26T12:56:50 Z Shin Sirni (COCI17_sirni) C++14
140 / 140
 3935 ms 721572 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

struct Disjoint_set {
    vector<int> lab;

    Disjoint_set(int n = 0) {
        lab.assign(n + 7, -1);
    }
    int root(int u) {
        return lab[u] < 0 ? u : lab[u] = root(lab[u]);
    }
    bool unite(int u, int v) {
        u = root(u); v = root(v);
        if (u == v) return false;
        if (lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }
};

const int MAX = 1e7;
int n;
int a[N];
int nxt[MAX + 7];
vector<pair<int, int>> val[MAX];

void solve(void) {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];

    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i ++) nxt[a[i]] = i;
    for (int i = MAX; i > 0; i --) if (nxt[i] == 0) {
        nxt[i] = nxt[i + 1];
    }

    for (int i = 1; i <= n; i ++) {
        if (nxt[a[i]] != i) val[0].emplace_back(i, nxt[a[i]]);
        if (nxt[a[i] + 1]) val[(a[nxt[a[i] + 1]] % a[i])].emplace_back(i, nxt[a[i] + 1]);
        for (int j = a[i] * 2; j <= MAX; j += a[i]) {
            if (!nxt[j]) break;
            if (j + a[i] >= a[nxt[j]]) {
                assert(a[nxt[j]] - j >= 0);
                val[a[nxt[j]] - j].emplace_back(i, nxt[j]);
            }
        }
    }

    long long res = 0;
    Disjoint_set dsu(n);
    for (int i = 0; i < MAX; i ++) {
        for (pair<int, int> x: val[i]) if (dsu.unite(x.fi, x.se)) {
            // cout << x.se << " " << x.fi << ' ' << i << '\n';
            res += i;
        }
    }
    cout << res;
}

int main(void) {
    cin.tie(0)->sync_with_stdio(0); 
    int test = 1;
    // cin >> test;
    while (test --) {
        solve();
    }
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 274420 KB Output is correct
2 Correct 208 ms 277428 KB Output is correct
3 Correct 186 ms 274544 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 274360 KB Output is correct
2 Correct 485 ms 275272 KB Output is correct
3 Correct 181 ms 274484 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 274320 KB Output is correct
2 Correct 170 ms 274264 KB Output is correct
3 Correct 171 ms 274392 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 285168 KB Output is correct
2 Correct 331 ms 323656 KB Output is correct
3 Correct 250 ms 295656 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 275988 KB Output is correct
2 Correct 1040 ms 543796 KB Output is correct
3 Correct 218 ms 287328 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 299460 KB Output is correct
2 Correct 409 ms 352864 KB Output is correct
3 Correct 232 ms 289424 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 278652 KB Output is correct
2 Correct 389 ms 343772 KB Output is correct
3 Correct 240 ms 294744 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 287816 KB Output is correct
2 Correct 1751 ms 572948 KB Output is correct
3 Correct 320 ms 290608 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 287668 KB Output is correct
2 Correct 3405 ms 685480 KB Output is correct
3 Correct 343 ms 297200 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 276716 KB Output is correct
2 Correct 3935 ms 721572 KB Output is correct
3 Correct 272 ms 296228 KB Output is correct