#868946 (C++14) No.2304 Distinct Elements

• 問題: No.2304 Distinct Elements
• ユーザー: kotatsugame
• 提出日時: 2023-05-12 22:47:23
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 172 ms / 3,000 ms
• コード長: 1,609 bytes
• コンパイル時間: 1,229 ms
• コンパイル使用メモリ: 91,976 KB
• 実行使用メモリ: 32,760 KB
• 最終ジャッジ日時: 2024-11-28 19:23:20
• 合計ジャッジ時間: 7,075 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 4
other	AC * 58

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<cassert>
using namespace std;
struct dat{
    long long Lc,Rc,Ls,Rs;
    map<int,int>cnt;
    int val;
    dat(){}
    dat(int v):Lc(0LL),Rc(0LL),Ls(0LL),Rs(0LL),val(v)
    {
        cnt.clear();
        cnt[v]=1;
    }
    long long need()
    {
        return Rs-Rc*val+Lc*val-Ls;
    }
    bool dec()
    {
        long long now=need();
        long long nLc=Lc,nRc=Rc,nLs=Ls,nRs=Rs;
        if(cnt.find(val)!=cnt.end())
        {
            int c=cnt[val];
            nRc+=c;
            nRs+=(long long)c*val;
        }
        if(cnt.find(val-1)!=cnt.end())
        {
            int c=cnt[val-1];
            nLc-=c;
            nLs-=(long long)c*(val-1);
        }
        long long nxt=nRs-nRc*(val-1)+nLc*(val-1)-nLs;
        if(nxt<=now)
        {
            val--;
            Lc=nLc;
            Rc=nRc;
            Ls=nLs;
            Rs=nRs;
            return true;
        }
        else return false;
    }
};
void merge(dat&l,dat&r)
{
    assert(l.val==r.val);
    l.Lc+=r.Lc;
    l.Rc+=r.Rc;
    l.Ls+=r.Ls;
    l.Rs+=r.Rs;
    if(l.cnt.size()<r.cnt.size())l.cnt.swap(r.cnt);
    for(pair<int,int>p:r.cnt)l.cnt[p.first]+=p.second;
}
int N,A[2<<17];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N;
    for(int i=0;i<N;i++)cin>>A[i];
    sort(A,A+N);
    for(int i=0;i<N;i++)A[i]-=i;
    vector<dat>S;
    S.push_back(dat(A[0]));
    for(int i=1;i<N;i++)
    {
        if(S.back().val<A[i])
        {
            S.push_back(dat(A[i]));
        }
        else
        {
            int v=S.back().val;
            if(v>A[i])S.back().Lc++,S.back().Ls+=A[i];
            S.back().cnt[A[i]]++;
            while(S.back().dec())
            {
                if(S.size()>=2&&S[S.size()-2].val==S.back().val)
                {
                    merge(S[S.size()-2],S.back());
                    S.pop_back();
                }
            }
        }
    }
    long long ans=0;
    for(int i=0;i<S.size();i++)ans+=S[i].need();
    cout<<ans<<endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX