提出 #70606778

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn = 5e5+5;
class B
{
public:
    int val,ans;
};
class A
{
public:
    int num,val;
    list<B>::iterator it;
    bool operator<(const A &that)const
    {
        return val<that.val;
    }
    bool operator>(const A &that)const
    {
        return num>that.num;
    }
}a[maxn];
long long res=0;
list<B> l;
void updata(list<B>::iterator it)
{
    int ans=2e9;
    if (it!=l.begin())
    {
        auto it2=it;
        it2--;
        ans=it->val-it2->val;
    }
    auto it2=it;
    it2++;
    if (it2!=l.end())
        ans=min(ans,it2->val-it->val);
    res-=it->ans;
    it->ans=ans;
    res+=ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i].val;
        a[i].num=i;
    }
    sort(a,a+n+1);
    for (int i=0;i<=n;i++)
        l.push_back({a[i].val,0});
    auto it=l.begin();
    for (int i=0;i<=n;i++)
    {
        a[i].it=it;
        it++;
    }
    for (auto i=l.begin();i!=l.end();i++)
        updata(i);
    stack<long long> s;
    sort(a,a+n+1,greater<A>());
    for (int i=0;i<n;i++)
    {
        s.push(res);
        auto it=a[i].it;
        vector<list<B>::iterator> itt;
        if (it!=l.begin())
        {
            auto it2=it;
            it2--;
            itt.push_back(it2);
        }
        auto it2=it;
        it2++;
        if (it2!=l.end())
            itt.push_back(it2);
        res-=it->ans;
        l.erase(it);
        for (auto j:itt)
            updata(j);
    }
    while (!s.empty())
    {
        print("{}\n",s.top());
        s.pop();
    }

}

提出情報

ジャッジ結果