oj.uz

답안 #1004424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1004424 2024-06-21T08:48:59 Z Nelt Sirni (COCI17_sirni) C++17
84 / 140
 1765 ms 786432 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll int
#define endl "\n"
 
using namespace std;
using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 1e5 + 5, MAX = 1e7 + 5;
struct Dsu
{
    ll n, ans;
    vector<ll> dsu;
    Dsu(ll sz = 1)
    {
        n = sz;
        ans = n;
        dsu.resize(n + 1, 0);
        init();
    }
    void init()
    {
        for (ll i = 0; i <= n; i++)
            dsu[i] = -1;
    }
    bool Union(ll x, ll y)
    {
        x = repr(x), y = repr(y);
        if (x == y)
            return false;
        if (dsu[x] < dsu[y])
            swap(x, y);
        ans--;
        dsu[y] += dsu[x];
        dsu[x] = y;
        return true;
    }
    ll repr(ll x)
    {
        if (dsu[x] < 0)
            return x;
        return dsu[x] = repr(dsu[x]);
    }
    ll query()
    {
        return ans;
    }
    ll size(ll x)
    {
        return -dsu[repr(x)];
    }
};
ll freq[MAX], ind[MAX];
vector<ll> consider[MAX];
vector<pair<ll, ll>> e[MAX];
ll best[N];
ll f(ll x, ll y)
{
    return min(x % y, y % x);
}
void solve()
{
    ll n;
    cin >> n;
    ll p[n];
    for (ll &i : p) cin >> i;
    long long ans = 0;
    {
        set<ll> s;
        for (ll i : p) s.insert(i);
        n = 0;
        for (ll i : s) p[n++] = i;
    }
    for (ll i = 0; i <= p[n - 1]; i++) ind[i] = -1;
    for (ll i : p) freq[i]++;
    for (ll i = 0; i < n; i++) ind[p[i]] = i;
    for (ll i = 1; i <= p[n - 1]; i++) freq[i] += freq[i - 1];
    for (ll i = 0; i < n; i++)
        for (ll j = p[i]; j <= p[n - 1]; j += p[i]) consider[j].push_back(i);
    Dsu dsu(n);
    for (ll i = 0; i < n - 1; i++) e[f(p[i], p[i + 1])].push_back(make_pair(i, i + 1));
    for (ll w = p[n - 1]; w > 0; w--)
    {
        ll pos = lower_bound(p, p + n, w) - p;
        if (pos < n)
        for (ll i : consider[w]) e[f(p[pos], p[i])].push_back(make_pair(pos, i));
    }
    // for (ll i = 0; i < n; i++) for (ll j = 0; j < n; j++) e[f(p[i], p[j])].push_back(make_pair(i, j));
    for (ll i = 0; i <= p[n - 1]; i++) for (auto [a, b] : e[i]) ans += dsu.Union(a, b) * i;
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 309 ms 548432 KB Output is correct
2 Correct 663 ms 639412 KB Output is correct
3 Correct 316 ms 548948 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 470636 KB Output is correct
2 Runtime error 571 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 308 ms 548688 KB Output is correct
2 Correct 304 ms 548128 KB Output is correct
3 Correct 339 ms 548992 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 342 ms 506504 KB Output is correct
2 Correct 609 ms 555460 KB Output is correct
3 Correct 455 ms 534060 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 484956 KB Output is correct
2 Correct 380 ms 525396 KB Output is correct
3 Correct 341 ms 500020 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 424 ms 527212 KB Output is correct
2 Correct 744 ms 589780 KB Output is correct
3 Correct 422 ms 526276 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 480380 KB Output is correct
2 Correct 754 ms 590844 KB Output is correct
3 Correct 425 ms 529624 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 615 ms 600136 KB Output is correct
2 Runtime error 960 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 687 ms 617096 KB Output is correct
2 Runtime error 1177 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 400 ms 556836 KB Output is correct
2 Runtime error 1765 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -