Submission #67787614

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

long long solve() {
    int N;
    cin >> N;

    long long ans = 0;
    vector<int> vec(N);
    map<int, vector<pair<int, int>>> mp;
    vector<int> rht_end(N);
    for (int i = 0; i < N; i++) {
        cin >> vec[i];
        mp[vec[i]].push_back(make_pair(i, i));
        rht_end[i] = i;
    }

    int mergecnt = 0;
    while (mergecnt < N - 1) {
        auto& fst = *mp.begin();
        sort(fst.second.begin(), fst.second.end());
        for (int i = 1; i < fst.second.size(); i++) {
            pair<int, int>& lft = fst.second[i - 1];
            pair<int, int>& rht = fst.second[i];
            if (lft.second == rht.first - 1) {
                vec[lft.first]++;
                mp[fst.first + 1].push_back(make_pair(lft.first, rht.second));
                rht_end[rht.second] = lft.first;
                lft = make_pair(-2, -2);
                rht = make_pair(-2, -2);
                mergecnt++;
            }
        }

        if (mergecnt == N - 1) {
            break;
        }

        for (int i = 0; i < fst.second.size(); i++) {
            pair<int, int> p = fst.second[i];
            if (p.first != -2) {
                int nxt = INT_MAX;
                if (p.first != 0) {
                    int l = rht_end[p.first - 1];
                    nxt = vec[l];
                }
                if (p.second != N - 1) {
                    nxt = min(nxt, vec[p.second + 1]);
                }
                vec[p.first] = nxt;
                ans += nxt - fst.first;
                mp[nxt].push_back(p);
            }
        }
        mp.erase(mp.begin());
    }
    
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cout << solve() << "\n";
    }
}

Submission Info

Compile Error

Main.cpp: In function ‘long long int solve()’:
Main.cpp:23:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   23 |         for (int i = 1; i < fst.second.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:40:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   40 |         for (int i = 0; i < fst.second.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~

Judge Result