Code in cpp

bash -lc cat > main.cpp << 'EOF' #include <bits/stdc++.h> using namespace std;

class Solution { public: using ll = long long; struct Node { ll sum; int cnt; int left; int right; Node(ll s=0,int c=0,int l=0,int r=0):sum(s),cnt(c),left(l),right(r){} };

text
vector<Node> seg;

int update(int prev, int l, int r, int pos, ll val) {
    int cur = (int)seg.size();
    seg.push_back(seg[prev]);
    seg[cur].sum += val;
    seg[cur].cnt += 1;
    if (l != r) {
        int m = (l + r) >> 1;
        if (pos <= m) {
            int child = update(seg[prev].left, l, m, pos, val);
            seg[cur].left = child;
        } else {
            int child = update(seg[prev].right, m+1, r, pos, val);
            seg[cur].right = child;
        }
    }
    return cur;
}

int kth(int nodeR, int nodeL, int l, int r, int k) {
    if (l == r) return l;
    int leftR = seg[nodeR].left;
    int leftL = seg[nodeL].left;
    int cntLeft = seg[leftR].cnt - seg[leftL].cnt;
    int m = (l + r) >> 1;
    if (k <= cntLeft) return kth(leftR, leftL, l, m, k);
    return kth(seg[nodeR].right, seg[nodeL].right, m+1, r, k - cntLeft);
}

pair<ll,ll> prefixQuery(int nodeR, int nodeL, int l, int r, int pos) {
    if (pos < l || (nodeR == 0 && nodeL == 0)) return {0LL, 0LL};
    if (r <= pos) {
        ll sum = seg[nodeR].sum - seg[nodeL].sum;
        ll cnt = (ll)seg[nodeR].cnt - (ll)seg[nodeL].cnt;
        return {sum, cnt};
    }
    int m = (l + r) >> 1;
    auto leftRes = prefixQuery(seg[nodeR].left, seg[nodeL].left, l, m, pos);
    if (pos <= m) return leftRes;
    auto rightRes = prefixQuery(seg[nodeR].right, seg[nodeL].right, m+1, r, pos);
    return {leftRes.first + rightRes.first, leftRes.second + rightRes.second};
}

vector<long long> minOperations(vector<int>& nums, int k, vector<vector<int>>& queries) {
    int n = (int)nums.size();
    vector<long long> ans;
    ans.reserve(queries.size());

    if (k == 0) {
        vector<int> diff(n,0), pref(n,0);
        for (int i = 1; i < n; ++i) {
            diff[i] = (nums[i] != nums[i-1]);
            pref[i] = pref[i-1] + diff[i];
        }
        for (auto &q : queries) {
            int l = q[0], r = q[1];
            if (l == r) { ans.push_back(0); continue; }
            if (pref[r] - pref[l] == 0) ans.push_back(0);
            else ans.push_back(-1);
        }
        return ans;
    }

    long long kk = llabs((long long)k);

    vector<ll> rem(n), scaled(n);
    for (int i = 0; i < n; ++i) {
        ll x = nums[i];
        ll r = ((x % kk) + kk) % kk;
        rem[i] = r;
        scaled[i] = (x - r) / kk;
    }

    vector<int> diff(n,0), pref(n,0);
    for (int i = 1; i < n; ++i) {
        diff[i] = (rem[i] != rem[i-1]);
        pref[i] = pref[i-1] + diff[i];
    }

    vector<ll> vals = scaled;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = (int)vals.size();

    vector<int> idx(n);
    for (int i = 0; i < n; ++i) {
        idx[i] = lower_bound(vals.begin(), vals.end(), scaled[i]) - vals.begin();
    }

    seg.clear();
    seg.reserve((n + 5) * 20);
    seg.push_back(Node());

    vector<int> root(n+1, 0);
    vector<ll> prefScaled(n+1, 0);
    for (int i = 0; i < n; ++i) {
        root[i+1] = update(root[i], 0, m-1, idx[i], scaled[i]);
        prefScaled[i+1] = prefScaled[i] + scaled[i];
    }

    for (auto &qvec : queries) {
        int l = qvec[0], r = qvec[1];
        int len = r - l + 1;

        if (l < r && pref[r] - pref[l] > 0) {
            ans.push_back(-1);
            continue;
        }

        if (len == 1) {
            ans.push_back(0);
            continue;
        }

        int rootR = root[r+1];
        int rootL = root[l];

        int kthPos = (len + 1) / 2;
        int medIndex = kth(rootR, rootL, 0, m-1, kthPos);
        ll medVal = vals[medIndex];

        ll totalSum = prefScaled[r+1] - prefScaled[l];
        auto [sumLE, cntLE] = prefixQuery(rootR, rootL, 0, m-1, medIndex);
        ll cntGT = (ll)len - cntLE;
        ll sumGT = totalSum - sumLE;
        ll cost = medVal * cntLE - sumLE + sumGT - medVal * cntGT;
        ans.push_back(cost);
    }

    return ans;
}

};

long long bruteOne(vector<int> nums, int k, int L, int R) { vector<int> sub(nums.begin()+L, nums.begin()+R+1); if (k == 0) { if (all_of(sub.begin()+1, sub.end(), [&](int x){return x==sub[0];})) return 0; else return -1; } long long kk = llabs((long long)k); vector<long long> rem(sub.size()); for (int i=0;i<(int)sub.size();++i){ long long x=sub[i]; rem[i]=((x%kk)+kk)%kk; } bool same=true; for (int i=1;i<(int)rem.size();++i) if(rem[i]!=rem[0]) same=false; if(!same) return -1; long long r=rem[0]; vector<long long> T(sub.size()); for (int i=0;i<(int)sub.size();++i) T[i]=(sub[i]-r)/kk; sort(T.begin(), T.end()); long long med = T[T.size()/2]; long long cost=0; for(long long v:T) cost+= llabs(v-med); return cost; }

int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);

text
mt19937 rng(0);
Solution sol;
for(int n=1;n<=20;++n){
    for(int k=-5;k<=5;++k){
        for(int it=0;it<200;++it){
            if(k==0 && rng()%2){} // allow
            vector<int> nums(n);
            for(int i=0;i<n;++i) nums[i]=(int) (rng()%11)-5; // -5..5
            int q = 5;
            vector<vector<int>> qs;
            for(int j=0;j<q;++j){
                int l=rng()%n; int r=rng()%n; if(l>r) swap(l,r); qs.push_back({l,r});
            }
            auto got = sol.minOperations(nums,k,qs);
            for(int j=0;j<q;++j){
                long long br = bruteOne(nums,k,qs[j][0],qs[j][1]);
                if(got[j]!=br){
                    cerr<<"mismatch n="<<n<<" k="<<k<<"\n";
                    cerr<<"nums:"; for(auto x:nums) cerr<<' '<<x; cerr<<"\n";
                    cerr<<"query "<<qs[j][0]<<","<<qs[j][1]<<" got="<<got[j]<<" br="<<br<<"\n";
                    return 0;
                }
            }
        }
    }
}
cerr<<"all good"<<"\n";
return 0;

} EOF

g++ -std=c++17 -O2 -pipe -static -s -o main main.cpp ./main

Thought for 13m 53s