Submission #67786024

---

Source Code Expand

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;



void test_case() {
    int n;
    cin >> n;
    vector <int> a(n);
    for (auto &i : a) cin >> i;
    ll ans = 0;
//    set <pii> val, pos;
//    for (int i = 0; i < n; i++) {
//        pos.insert({i, a[i]});
//        val.insert({a[i], i});
//    }
//    while (len(val) > 1) {
//        int cur_pos = val.begin()->second;
//        int cur_val = val.begin()->first;
////        LOG(cur_pos, cur_val);
//        auto it = pos.find({cur_pos, cur_val});
//        if (next(it) != pos.end() && next(it)->second == cur_val) {
//            auto gg = next(it);
//            val.erase(val.begin());
//            val.erase(make_pair(gg->second, gg->first));
//            pos.erase(it);
//            pos.erase(gg);
//            val.insert({cur_val + 1, cur_pos});
//            pos.insert({cur_pos, cur_val + 1});
//        }
//        else {
//            ++ans;
//            val.erase(val.begin());
//            pos.erase(it);
//            val.insert({cur_val + 1, cur_pos});
//            pos.insert({cur_pos, cur_val + 1});
//        }
//    }
    vector <pii> b(n);
    for (int i = 0; i < n; i++) {
        b[i] = make_pair(a[i], i);
    }
    sort(all(b));
    int cnt = 0, last = 0;
    set <int> pos;
    vector <int> active(n);
    for (int i = 0; i < n; i++) {
        pos.insert(i);
    }

    set <pii> save;

    auto make_op = [&] (int id, int val) {
//        LOG(id, val, ans);



        ans += (val - last) * 1ll * cnt;

        auto it = pos.find(id);

//        LOG(it == pos.end());


        if (it != pos.begin() && active[*prev(it)] == 1) {
            save.insert({val + 1, id});
            pos.erase(prev(it));
            --cnt;
            active[id] = 2;
        }
        else if (next(it) != pos.end() && active[*next(it)] == 1) {
            save.insert({val + 1, id});
            pos.erase(next(it));
            --cnt;
            active[id] = 2;
        }
        else {
            ++cnt;
            active[id] = 1;
        }







        last = val;

    };
    for (int i = 0; i < n; i++) {
        save.insert(b[i]);
    }
    while (!save.empty()) {
        int id = save.begin()->second;
        int val = save.begin()->first;
        save.erase(save.begin());
        make_op(id, val);


    }
//    for (int i = 0; i < n || !save.empty();) {
//
//
//
//
//
//
//        int id = b[i].second;
//        make_op(id, b[i].first);
//
//        ++i;
//    }
    cout << ans << '\n';
    LOG(ans);
}



int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;

     cin >> t;

    while (t--) test_case();

    return 0;
}

/*
KoRoVa!
*/

Submission Info

Judge Result