Submission #67786645

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
#include <limits>
#include <array>

static const int MOD = 998244353;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

void solve(){
    int n;
    cin >> n;
    vector<int> A(n);
    for (auto &&i : A) scanf("%d", &i);
    vector<pair<int, int>> rle;
    rle.emplace_back(A[0], 1);
    for (int i = 1; i < n; ++i) {
        if(A[i] == rle.back().first){
            rle.back().second++;
        }else {
            rle.emplace_back(A[i], 1);
        }
    }
    int m = rle.size();
    vector<int> L(m), R(m);
    for (int i = 0; i < m; ++i) {
        L[i] = i-1;
        R[i] = (i+1 < m ? i+1 : -1);
    }
    vector<int> ord(m);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return rle[i].first < rle[j].first;
    });
    ll ans = 0;
    for (auto &&x: ord) {
        if(rle[x].second == 0) continue;
        int lval = (L[x] >= 0 ? rle[L[x]].first : -1);
        int rval = (R[x] >= 0 ? rle[R[x]].first : -1);
        int lx = L[x], rx = R[x];
        int val = (lval == -1 ? rval : (rval == -1 ? lval : min(lval, rval)));
        if(val == -1) continue;
        while(rle[x].first < val){
            if(rle[x].second != 1){
                if(rle[x].second&1){
                    ans++;
                    rle[x].second++;
                }
                rle[x].second /= 2;
                rle[x].first++;
            }else {
                ans += val - rle[x].first;
                rle[x].first = val;
            }
        }
        if(lval == rval){
            int k = rle[R[x]].second + rle[x].second + rle[L[x]].second;
            rle[lx].second = k;
            R[lx] = R[rx];
            if(R[rx] >= 0) L[R[rx]] = lx;
            rle[x].second = 0; L[x] = R[x] = -1;
            rle[rx].second = 0; L[rx] = R[rx] = -1;
        }else if(val == lval){
            rle[lx].second += rle[x].second;
            rle[x].second = 0;
            R[lx] = R[x];
            if(R[x] >= 0) L[R[x]] = lx;
        }else if(val == rval) {
            rle[rx].second += rle[x].second;
            rle[x].second = 0;
            L[rx] = L[x];
            if(L[x] >= 0) R[L[x]] = rx;
        }
    }
    for (int i = 0; i < m; ++i) {
        while(rle[i].second > 1){
            if(rle[i].second & 1){
                ans++;
                rle[i].second++;
            }
            rle[i].second /= 2;
            rle[i].first++;
        }
    }
    cout << ans << "\n";
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:25:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   25 |     for (auto &&i : A) scanf("%d", &i);
      |                        ~~~~~^~~~~~~~~~

Judge Result