結果

問題 No.2046 Ans Mod? Mod Ans!
ユーザー asaringoasaringo
提出日時 2023-11-08 02:38:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,227 ms / 4,000 ms
コード長 10,682 bytes
コンパイル時間 2,506 ms
コンパイル使用メモリ 218,992 KB
実行使用メモリ 22,912 KB
最終ジャッジ日時 2024-09-25 23:33:26
合計ジャッジ時間 10,462 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
21,248 KB
testcase_01 AC 55 ms
21,248 KB
testcase_02 AC 116 ms
21,320 KB
testcase_03 AC 341 ms
21,232 KB
testcase_04 AC 227 ms
21,376 KB
testcase_05 AC 340 ms
21,248 KB
testcase_06 AC 248 ms
21,248 KB
testcase_07 AC 323 ms
21,376 KB
testcase_08 AC 32 ms
21,376 KB
testcase_09 AC 31 ms
21,376 KB
testcase_10 AC 34 ms
21,376 KB
testcase_11 AC 44 ms
21,504 KB
testcase_12 AC 42 ms
21,248 KB
testcase_13 AC 443 ms
21,888 KB
testcase_14 AC 355 ms
21,804 KB
testcase_15 AC 661 ms
22,256 KB
testcase_16 AC 705 ms
22,272 KB
testcase_17 AC 565 ms
22,144 KB
testcase_18 AC 914 ms
22,016 KB
testcase_19 AC 510 ms
22,144 KB
testcase_20 AC 1,227 ms
22,912 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define overload2(a, b, c, ...) c
#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e ...) e
#define overload5(a, b, c, d, e, f ...) f
#define overload6(a, b, c, d, e, f, g ...) g
#define fast_io ios::sync_with_stdio(false); cin.tie(nullptr);
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
typedef long long ll;
typedef long double ld;
#define chmin(a,b) a = min(a,b);
#define chmax(a,b) a = max(a,b);
#define bit_count(x) __builtin_popcountll(x)
#define leading_zero_count(x) __builtin_clz(x)
#define trailing_zero_count(x) __builtin_ctz(x)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a / gcd(a,b) * b
#define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__)
#define rep1(i,n) for(int i = 0 ; i < n ; i++)
#define rrep(i,a,b) for(int i = a ; i < b ; i++)
#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)
#define pt(a) cout << a << endl;
#define print(...) printall(__VA_ARGS__);
#define debug(a) cout << #a << " " << a << endl;
#define all(a) a.begin(), a.end()
#define endl "\n";
#define v1(T,n,a) vector<T>(n,a)
#define v2(T,n,m,a) vector<vector<T>>(n,v1(T,m,a))
#define v3(T,n,m,k,a) vector<vector<vector<T>>>(n,v2(T,m,k,a))
#define v4(T,n,m,k,l,a) vector<vector<vector<vector<T>>>>(n,v3(T,m,k,l,a))
template<typename T,typename U>istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T,typename U>ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T>istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>istream &operator>>(istream&is,vector<vector<T>>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<vector<T>>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const set<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const multiset<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<class... Args> void printall(Args... args){for(auto i:initializer_list<common_type_t<Args...>>{args...}) cout<<i<<" ";cout<<endl;}

template<typename S, S (*op)(S, S), S (*e)(), typename M, S (*mapping)(M, S), M (*composition)(M, M), M (*id)()> struct LazySegmentTree{
    private:
        int size, log, _n;
        vector<S> d;
        vector<M> lz;

        void init_(S ev, M idv, int size) { d = {}; lz = {}; d.resize(2*size,ev); lz.resize(size,idv); }
        
        void build(vector<S> V){
            size = 1;
            log = 0;
            while(size < _n) size *= 2, log++;
            d = std::vector<S>(2 * size, e());
            lz = std::vector<M>(size, id());
            for (int i = 0; i < _n; i++) d[size + i] = V[i];
            for (int i = size - 1; i >= 1; i--) update(i);
        }

        // 与えられたMの値をapplyし、遅延配列にcompositionする
        void all_apply(int k, M f) {
            d[k] = mapping(f, d[k]);
            if (k < size) lz[k] = composition(f, lz[k]);
        }

        // 自身の遅延配列を子要素に振り分け、自身の遅延配列をMの単位元にする
        void push(int k) {
            all_apply(2 * k, lz[k]);
            all_apply(2 * k + 1, lz[k]);
            lz[k] = id();
        }

        // 親のノード = 子ノード同士のop演算結果となる
        void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }

        void set_(int p, S x) {
            assert(0 <= p && p < _n);
            p += size;
            for (int i = log; i >= 1; i--) push(p >> i);
            d[p] = x;
            for (int i = 1; i <= log; i++) update(p >> i);
        }

        S get_(int p) {
            assert(0 <= p && p < _n);
            p += size;
            for (int i = log; i >= 1; i--) push(p >> i);
            return d[p];
        }
        
        void apply_(int p, M f) {
            assert(0 <= p && p < _n);
            p += size;
            for (int i = log; i >= 1; i--) push(p >> i);
            d[p] = mapping(f, d[p]);
            for (int i = 1; i <= log; i++) update(p >> i);
        }
        void apply_(int l, int r, M f) {
            assert(0 <= l && l <= r && r <= _n);
            if (l == r) return;

            l += size;
            r += size;

            for (int i = log; i >= 1; i--) {
                // l, rが葉から登っていく際に、現在自分がいるノードの遅延配列をmappingする必要がある。
                // しかし、遅延セグメント木のアルゴリズムの関係上、本来格納されているはずの遅延配列上の値が自分のノードにはなく、親がもっていることがある。
                // そのため、親から前もって自身のノードが持べき遅延配列の値をもらっておく必要がある。
                // よって、このapply_関数上では、l, rの繊維先ノードで必要となる遅延配列の値（必要となる値のみ）を前もって子ノードに振り分けておく
                if (((l >> i) << i) != l) push(l >> i);
                if (((r >> i) << i) != r) push((r - 1) >> i);
            }

            {
                int l2 = l, r2 = r;
                while (l < r) {
                    if (l & 1) all_apply(l++, f);
                    if (r & 1) all_apply(--r, f);
                    l >>= 1;
                    r >>= 1;
                }
                l = l2;
                r = r2;
            }

            for (int i = 1; i <= log; i++) {
                if (((l >> i) << i) != l) update(l >> i);
                if (((r >> i) << i) != r) update((r - 1) >> i);
            }
        }


        S prod_(int l, int r) {
            assert(0 <= l && l <= r && r <= _n);
            if (l == r) return e();

            l += size;
            r += size;

            for (int i = log; i >= 1; i--) {
                if (((l >> i) << i) != l) push(l >> i);
                if (((r >> i) << i) != r) push((r - 1) >> i);
            }

            S sml = e(), smr = e();
            while (l < r) {
                if (l & 1) sml = op(sml, d[l++]);
                if (r & 1) smr = op(d[--r], smr);
                l >>= 1;
                r >>= 1;
            }

            return op(sml, smr);
        }

        S all_prod_() { return d[1]; }

        template <bool (*g)(S)> int max_right_(int l) {
            return max_right_(l, [](S x) { return g(x); });
        }
        template <class G> int max_right_(int l, G g) {
            assert(0 <= l && l <= _n);
            assert(g(e()));
            if (l == _n) return _n;
            l += size;
            for (int i = log; i >= 1; i--) push(l >> i);
            S sm = e();
            do {
                while (l % 2 == 0) l >>= 1;
                if (!g(op(sm, d[l]))) {
                    while (l < size) {
                        push(l);
                        l = (2 * l);
                        if (g(op(sm, d[l]))) {
                            sm = op(sm, d[l]);
                            l++;
                        }
                    }
                    return l - size;
                }
                sm = op(sm, d[l]);
                l++;
            } while ((l & -l) != l);
            return _n;
        }

        template <bool (*g)(S)> int min_left_(int r) {
            return min_left_(r, [](S x) { return g(x); });
        }
        template <class G> int min_left_(int r, G g) {
            assert(0 <= r && r <= _n);
            assert(g(e()));
            if (r == 0) return 0;
            r += size;
            for (int i = log; i >= 1; i--) push((r - 1) >> i);
            S sm = e();
            do {
                r--;
                while (r > 1 && (r % 2)) r >>= 1;
                if (!g(op(d[r], sm))) {
                    while (r < size) {
                        push(r);
                        r = (2 * r + 1);
                        if (g(op(d[r], sm))) {
                            sm = op(d[r], sm);
                            r--;
                        }
                    }
                    return r + 1 - size;
                }
                sm = op(d[r], sm);
            } while ((r & -r) != r);
            return 0;
        }

    public:
        LazySegmentTree(int n): LazySegmentTree(vector<S>(n, e())) {}
        LazySegmentTree(const vector<S>& V): _n((int)V.size()) { build(V); }
        void init(S ev = e(), M idv = id()) { init_(ev, idv); }
        void set(int p, S x) { set_(p,x); }
        void apply(int k, M x) { apply_(k, x); }
        void apply(int l, int r, M x) { apply_(l, r, x); }
        S get(int k) { return get_(k); }
        S prod(int l, int r) { return prod_(l, r); }
        S all_prod() { return all_prod_(); }
        template<bool (*f)(S)> int max_right(int l) { return max_right_<f>(l); }
        template<bool (*f)(S)> int min_left(int  r) { return min_left_<f>(r); }
};

// 区間和を取るときはSにsizeを持たせる(以下のmonoidのmappingの箇所を参考にする)
namespace monoid{
    struct S{ ll sum; int size; };
    S e() { return S{(ll)0, 0}; }
    S op(S x , S y) { return S{ x.sum + y.sum, x.size + y.size }; }
    struct M{ ll a; };
    M id() { return M{0}; }
    S mapping(M x , S y) { return S{ x.a * y.size + y.sum, y.size }; }
    M composition(M x, M y) { return M{ x.a + y.a }; }
    int target;
    auto f = [](S x) -> bool { return x.sum < target; };
} using namespace monoid;


int n;

void solve(){
    cin >> n;
    vector<ll> A(n), I(202020);
    cin >> A;
    rep(i,n) I[A[i]]++;
    sort(all(A));
    ll res = 0;
    rep(i,n) {
        auto it = upper_bound(all(A), A[i]);
        int id = it - A.begin();
        res += A[i] * (n - id);
    }
    vector<S> vec(202020);
    rep(i,202020) vec[i] = {0,1};

    LazySegmentTree<S, op, e, M, mapping, composition, id> segtree(vec);
    rep(i,n) segtree.apply(A[i],A[i]+1,{A[i]});
    rep(i,1,202020){
        if(I[i] == 0) continue;
        for(ll x = i; x < 202020; x += i){
            ll cnt = upper_bound(all(A),x+i-1) - lower_bound(all(A),x);
            res -= segtree.prod(x,min(x+i,(ll)202020)).sum * I[i] - cnt * x * I[i];
        }
    }
    pt(res)
}

int main(){
    fast_io
    int t = 1;
    // cin >> t;
    rep(i,t) solve();
}
0