Submission #1461351

---

Source Code Expand

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

vector<long long> solve(int N, const vector<int> &A){
    vector<pair<int, int>> vis;
    vis.reserve(N);
    for (int i = 0; i != N; ++i) vis.emplace_back(make_pair(A[i], i));
    sort(vis.begin(), vis.end());
    vector<int> val;
    vector<int> freq;
    vector<int> min_idx;
    val.push_back(vis[N - 1].first);
    min_idx.push_back(vis[N - 1].second);
    freq.push_back(1);
    for (int i = N - 2; i >= 0; --i){
        auto vi = vis[i];
        if (vi.first == val.back()){
            min_idx.back() = vi.second;
            ++freq.back();
        }else{
            val.push_back(vi.first);
            min_idx.push_back(vi.second);
            freq.push_back(1);
        }
    }
    vector<long long> ret(N, 0);
    long long cum = freq[0];
    int idx = min_idx[0];
    for (int i = 1; i != val.size(); ++i){
        ret[idx] += (val[i - 1] - val[i]) * cum;
        idx = min(idx, min_idx[i]);
        cum += freq[i];
    }
    ret[idx] += val.back() * cum;
    return ret;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto & a : A) cin >> a;
    auto freq = solve(N, A);
    for (auto f : freq) cout << f << '\n';
    return 0;
}

Submission Info

Judge Result