We can construct a solution by fixing all $$$x_i$$$ as $$$x_c$$$ or all $$$y_i$$$ as $$$y_c$$$. For example, if we fix all $$$y_i$$$ as $$$y_c$$$, then we can output pairs $$$(x_c-1, y_c), (x_c+1, y_c), (x_c-2, y_c), (x_c+2, y_c), ... , (x_c- \lfloor \frac{k}{2} \rfloor, y_c), (x_c + \lfloor \frac{k}{2} \rfloor, y_c)$$$. If the $$$k$$$ is odd, we need one more pair, so just output $$$(x_c, y_c)$$$.

#include <iostream>
using namespace std;

int main() {
	int t; cin >> t;
	while(t--){
		int x, y, k; cin >> x >> y >> k;
		for(int i = 0; i < k - k % 2; i++){
			cout << x - (i & 1 ? 1 : -1) * (i / 2 + 1) << " " << y << "\n";
		} 
		if(k & 1){
			cout << x << " " << y << "\n";
		}
	}
}

We can always construct a solution such that the number of pairs $$$(i, j)$$$ is $$$1$$$ where the only pair is $$$(1, n)$$$. There exists several constructions, such as rotating $$$p$$$ once or increment all $$$p_i$$$ (and $$$p_i = n$$$ turns into $$$p_i = 1$$$).

Consider the former construction, where $$$q = [p_2, p_3, ..., p_n, p_1]$$$. For an arbitrarily interval $$$[i, j]$$$, $$$p[i..j]$$$ and $$$q[i..j]$$$ will have exactly $$$1$$$ element that's different, disregarding ordering. Since we have a permutation and all elements are distinct, the sum in the range will never be the same. The only exception is the entire array, of course.

#include <bits/stdc++.h>
using namespace std;

int main(){
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		vector<int> p(n);
		for(int& i: p) cin >> i;
		rotate(p.begin(), p.begin() + 1, p.end());
		for(int i: p) cout << i << " ";
		cout << "\n";
	}
}

First, solve for $$$k = 0$$$. Find some nice characterization about $$$med(c_i)$$$ and thus the maximum score.

Divide into $$$2$$$ cases where we either increment the max element or the median.

Apply binary search

Let's forget about the operations of adding $$$1$$$ to $$$a_i$$$ and figure out how to find an array's score. Assume the array $$$a$$$ is sorted in increasing order as the order doesnt change the problem.

First observe how $$$med(c_i)$$$ changes with respect to $$$i$$$. $$$med(c_i)$$$ is always either $$$a_{\lfloor \frac{n}{2} \rfloor}$$$ or $$$a_{\lfloor \frac{n + 2}{2} \rfloor}$$$. You can prove this formally by considering different positions of $$$i$$$ with respect to the initial median position. Specifically, for all $$$i \le \lfloor \frac{n}{2} \rfloor$$$, $$$med(c_i) = a_{\lfloor \frac{n + 2}{2} \rfloor}$$$, and for other $$$i$$$, $$$med(c_i) = a_{\lfloor \frac{n}{2} \rfloor}$$$.

Claim 1 : The score of the final array (after sorting in increasing order) is $$$a_n + med(c_n)$$$

Hence, our score can be nicely characterized by "max + median of the others".

Claim 2 : Either we will use all $$$k$$$ operations on the element which eventually becomes max element in our array, or we will use all operations trying to improve $$$med(c_n)$$$ and keep max element constant.

Thus, we are in $$$2$$$ cases now, either increase max, or increase median of the rest. We will solve the problem considering both cases separately.

Case $$$1$$$ : We do operations on the element which becomes max eventually.

Case 2 : We do operations to increase the median of the others.

Thus, the problem is solved in $$$O(N \cdot log (MAX))$$$. The code is nicely written and commented, you may want to check it out.

#include <bits/stdc++.h> 
using namespace std;

int main(){
    int t; cin >> t;
    
    while (t--){
        int n, k; cin >> n >> k;
        
        vector <pair<int, int>> a(n);
        for (auto &x : a) cin >> x.first;
        for (auto &x : a) cin >> x.second;
        sort(a.begin(), a.end());
        
        long long ans = 0;
        // case 1 : increment max 
        for (int i = 0; i < n; i++) if (a[i].second == 1){
            // find med(c_i) 
            int mc;
            if (i < n / 2) mc = a[n / 2].first;
            else mc = a[(n - 2) / 2].first;
            
            ans = max(ans, 0LL + a[i].first + k + mc);
        }
        
        // case 2 : increment median
        int lo = 0, hi = 2e9;
        while (lo != hi){
            int mid = (1LL + lo + hi) / 2;
            
            int z = 0;
            vector <int> smaller_list;
            for (int i = 0; i < n - 1; i++){
                if (a[i].first >= mid){
                    z++;
                } else if (a[i].second == 1){
                    smaller_list.push_back(mid - a[i].first); // list of numbers smaller than x but b[i] = 1 
                }
            }
            
            reverse(smaller_list.begin(), smaller_list.end()); // list will be sorted in ascending, but we want sorted in descending, as greedily changing largest elements 
            int kk = k;
            for (auto x : smaller_list) if (kk >= x){
                kk -= x;
                z++;
            }
            
            if (z >= (n + 1) / 2) lo = mid;
            else hi = mid - 1;
        }
        
        ans = max(ans, 0LL + a[n - 1].first + lo);
        
        cout << ans << "\n";
    }
    return 0;
}

First, let's consider if there was no alternative bridges. Then obviously, if Bessie starts at island $$$i$$$ and keeps moving forwards, it is impossible for Elsie to move past island $$$i$$$ since the bridge would have already collapsed. From this, we can deduce that Bessie cannot let Elsie use these alternative bridges to overtake the island Bessie is on, or else Elsie will always reach the end first.

Therefore, Bessie will keep moving right in hopes of breaking enough bridges so that it is impossible to for Elsie to overtake Bessie. This can be simplified to: consider we are at island $$$i$$$ and $$$t$$$ units of time has passed, for all alternative bridges that Elsie can take with an endpoint $$$v > i + t$$$, we have to reach $$$v$$$ before her.

Let $$$d_i$$$ denote the minimum amount of time Elsie takes to reach island $$$i$$$. For the first case, consider all bridges with endpoints $$$v > S$$$, then $$$d_v \geq v - S - 1$$$ must hold true since we want to reach $$$v$$$ before Elsie does when we keep going right. We can rearrange the equation as $$$S \geq v - d_v - 1$$$. To make sure this holds true for all bridges, we just have to make sure this is true for the maximum value of $$$v - d_v$$$.

All $$$d_i$$$ can be calculated using a linear sweep to the right, and we can track all $$$v - d_v$$$ with a sweep to the left. Note that we cannot take a bridge if it starts past $$$S$$$, so we need to track the maximum with a multiset and erasing as we sweep.

Time Complexity is $$$\mathcal{O}(n \log n)$$$. There exists other solutions using prefix sums in $$$\mathcal{O}(n)$$$ and segment tree in $$$\mathcal{O}(n \log n)$$$

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define trav(a,x) for(auto& a: x)

void solve() {
	int n, m; cin >> n >> m;
	vector<vector<int>> g(n), rg(n);
	FOR(i,0,m){
		int u, v; cin >> u >> v;
		--u; --v;
		g[u].pb(v);
		rg[v].pb(u);
	}
	FOR(i,0,n-1) g[i].pb(i+1);
	vector<int> dist(n, -1);
	queue<int> q;
	dist[0] = 0;
	q.push(0);
	while(!q.empty()){
		int f = q.front();
		q.pop();
		trav(i, g[f]){
			if(dist[i] == -1){
				dist[i] = dist[f] + 1;
				q.push(i);
			}
		}
	}
	multiset<int> max_good_rights;
	vector<vector<int>> to_erase(n);
	string ans = string(n - 1, '0');
	ROF(i,n-1,0){
		trav(j, rg[i]){
			int max_right = i - dist[j];
			max_good_rights.insert(max_right);
			to_erase[j].pb(max_right);
		}
		trav(j, to_erase[i]){
			max_good_rights.erase(max_good_rights.find(j));
		}
		if(i < n - 1){
			int max_good_right = max_good_rights.empty() ? -1 : *prev(max_good_rights.end());
			if(i >= max_good_right - 1){
				ans[i] = '1';
			}
		}
	}
	cout << ans << endl;
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	int t = 1;
	cin >> t;
	for(int test = 1; test <= t; test++){
		solve();
	}
}

Consider the ball with the maximum number. Let this ball be $$$m$$$. That ball can clearly be the last ball remaining. And if we are able to merge some ball $$$i$$$ with ball $$$m$$$ (whilst removing $$$m$$$), then ball $$$i$$$ can also be the last ball remaining.

We can do a divide and conquer solution. For some range $$$[l,r]$$$, let $$$m$$$ be the ball with the maximum value. Clearly, $$$m$$$ can be the last ball remaining if we only consider the range $$$[l, r]$$$.

Let's first recurse on $$$[l,m)$$$ and $$$(m,r]$$$. Let $$$s_l=a_l+a_{l+1}+\cdots+a_{m-1}$$$ (i.e. the sum of the left half). If $$$s_l < a_m$$$ then no ball in the left half can be the last one remaining. Otherwise, the results (i.e. whether each ball can be the last one standing) for range $$$[l,r]$$$ for balls in $$$[l,m)$$$ is the results we computer when recursing onto $$$[l,m)$$$. The same reasoning holds for the right half.

We can use a sparse table to find the maximum ball in any range. This leads to a $$$\mathcal{O}(n\log n)$$$ solution.

#include <bits/stdc++.h>
using namespace std; 

#define ll long long
#define pll pair<ll, ll>

const int MAX = 2e5 + 5;

int n, x, ans; ll A[MAX], bad[MAX], P[MAX]; pll rmq[MAX][18];

void dnq(int l, int r){
    if (l >= r)
        return;
    
    int lg = 31 - __builtin_clz(r - l + 1);
    int mid = max(rmq[l][lg], rmq[r - (1 << lg) + 1][lg]).second;
    
    dnq(l, mid - 1);
    dnq(mid + 1, r);

    ll sum1 = P[mid - 1] - P[l - 1];
    ll sum2 = P[r] - P[mid];

    // Left half bad
    if (A[mid] > sum1){
        bad[l] += 1;
        bad[mid] += -1;
    }
    // Right half bad
    if (A[mid] > sum2){
        bad[mid + 1] += 1;
        bad[r + 1] += -1;
    }
}

void solve(){
    cin >> n >> x;

    for (int i = 1; i <= n; i++){
        cin >> A[i];
        P[i] = P[i - 1] + A[i];
        bad[i] = 0;
        rmq[i][0] = {A[i], i};
    }
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
    
    dnq(1, n);

    ans = 0;

    for (int i = 1; i <= n; i++){
        bad[i] += bad[i - 1];
        ans += !bad[i];
    }
    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

For some ball $$$i$$$, let $$$l_i$$$ and $$$r_i$$$ be the first balls on the left and right that have a value greater than $$$a_i$$$.

Proccess the balls from largest $$$a_i$$$ to smallest $$$a_i$$$. For each ball $$$i$$$, let $$$\text{ans}_i$$$ denote whether it can be the last ball remaining. We know that if we merge ball $$$i$$$ with some ball $$$j$$$ (while discarding $$$j$$$) and $$$\text{ans}_j=1$$$, then $$$\text{ans}_i=1$$$. Furthermore, we know that balls $$$l_i$$$ and $$$r_i$$$ can freely merge with balls $$$j$$$ where $$$j$$$ is in interval $$$[l_i+1 \ldots r_i-1]$$$ while discarding $$$j$$$ (i.e. $$$\text{ans}_{l_i}$$$ and $$$\text{ans}_{r_i}$$$ would have taken this into account).

This motivates the following idea. Let $$$s$$$ be the sum of values in $$$[l_i+1 \ldots r_i-1]$$$. If $$$s \geq a_{l_i}$$$ then we do $$$\text{ans}_i := \text{ans}_i |\text{ans}_{l_i}$$$. Similarly, if $$$s \geq a_{r_i}$$$, then we do $$$\text{ans}_i := \text{ans}_i |\text{ans}_{r_i}$$$. This solution runs in $$$\mathcal{O}(n \log n)$$$ due to sorting.

#include <bits/stdc++.h>
using namespace std; 

#define ll long long

void solve(){
    int n, x;
    cin >> n >> x;

    vector<int> A(n + 5);
    vector<ll> P(n + 5);
    vector<int> ans(n + 5, 0);
    vector<int> ord(n);
    set<int> S{0, n + 1};

    for (int i = 1; i <= n; i++){
        cin >> A[i];
        P[i] = P[i - 1] + A[i];
        ord.push_back(i);
    }
    sort(ord.begin(), ord.end(), [&](int a, int b){
        return A[a] > A[b];
    });
    for (int i : ord){
        int l = *(--S.lower_bound(i));
        int r = *S.lower_bound(i);
        ll sum = P[r - 1] - P[l];

        if (i == ord[0])
            ans[i] = true;
        if (sum >= A[l])
            ans[i] |= ans[l];
        if (sum >= A[r])
            ans[i] |= ans[r];
        
        S.insert(i);
    }
    cout << accumulate(ans.begin(), ans.end(), 0) << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

Consider the naive greedy solution. We continuously merge with the balls on the left and right without removing our ball until we can't anymore or our ball is the final remaining one.

Suppose at some point in this greedy approach, we can not merge with the balls on our left and right anymore without discarding our ball. Let our ball be $$$i$$$. Then we have the following cases.

1. There is a ball $$$l$$$ on the left of $$$i$$$ and ball $$$r$$$ on the right of $$$i$$$. Then: $$$\min(a_l,a_r) > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$.
2. There is a ball $$$l$$$ on the left of $$$i$$$ but no ball on the right of $$$i$$$. Then: $$$a_l > a_{l+1}+a_{l+2}+\cdots+a_{\text{last}}$$$.
3. There exists no ball on the left of $$$i$$$ but a ball $$$r$$$ on the right of $$$i$$$. Then: $$$a_r > a_1+a_2+\cdots+a_{r-1}$$$.

For some ball $$$i$$$, if there exists some $$$l$$$ and/or some $$$r$$$ such that one of the above is true, then there exists no way for our ball to be the last one remaining. Otherwise, the ball can be the last one remaining.

Let $$$p$$$ be the prefix sum array of $$$a$$$ (i.e. $$$p_i=a_1+a_2+\cdots+a_i$$$).

For some ball $$$i$$$, we want to do the following.

1. Find the smallest $$$r_1$$$ such that there exists some $$$l$$$ such that ($$$l, r_1$$$) is a pair (i.e. $$$\min(a_l,a_{r_1}) > a_{l+1}+a_{l+2}+\cdots+a_{r_1-1}$$$). Finding this is more difficult than the other cases and will be focused on later.
2. Find the smallest $$$r_2$$$ such that $$$a_{r_2} > a_1+a_2+\cdots+a_{{r_r}-1}$$$. We can rewrite it as as $$$a_{r_2} > p_{r_2-1}$$$ and it can easily be found.
3. Find the smallest $$$r_l$$$ such that there exists no $$$l$$$ on the left of $$$i$$$ such that $$$a_l > a_{l+1}+a_{l+2}+\cdots+a_{r_l}$$$. We can rewrite the inequality as finding the first $$$r_l$$$ such that $$$p_{r_l} \geq a_l + p_l$$$ which can be done with binary search.

Suppose at some $$$i$$$, we know its $$$r_l$$$, $$$r_1$$$, and $$$r_{2}$$$. Then we know ball $$$i$$$ can be the last one remaining for prefixes spanning from $$$r_l$$$ to $$$\min(r_1-1, r_{2}-1)$$$ so we can do a range add with prefix sums.

The only thing we have not resolved yet is how to find the smallest $$$r_1$$$ for some $$$i$$$ such that $$$\min(a_l,a_{r_1}) > a_{l+1}+a_{l+2}+\cdots+a_{r_1-1}$$$.

Let's iterate over $$$r$$$. For each $$$r$$$ we want to find the leftmost $$$l$$$ such that $$$\min(a_l,a_{r}) > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$

A key observation is that we can write the following inequality as $$$a_l > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$ and $$$a_r > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$ (both have to be true).

Using prefix sums, the equations can be rewritten as $$$a_l + p_l > p_{r-1}$$$ and $$$p_l > p_{r-1} - a_r$$$.

So some $$$(l,r)$$$ works if the equation above is satisfied. Consider the second part $$$p_l > p_{r-1} - a_r$$$. We can binary search to find the range of available $$$l$$$ that satisfy this. Specifically, let $$$l_b$$$ be the lower bound of the range. Then, any $$$l$$$ in $$$[l_b...i)$$$ satisfies this.

Now, let's try to satisfy $$$a_l + p_l > p_{r-1}$$$. Unfortunately, $$$a_l + p_l$$$ is not monotonic so the method above will not work. Instead, we can create a sparse table over all $$$a_i + p_i$$$. Then we can binary search to find the first $$$l_{opt}$$$ such that the maximum in range $$$[l_b,l_{opt}]$$$ (which can be found with the sparse table) is greater than $$$p_{r-1}$$$.

Circling back, $$$r_1$$$ is the minimum $$$r$$$ of an interval covering $$$i$$$ which can be found with things such as sweepline. In all, this solution runs in $$$\mathcal{O}(n \log n)$$$ time.

#include <bits/stdc++.h>
using namespace std;

#define ll long long

void solve(){
    int n, x;
    cin >> n >> x;

    vector<ll> A(n + 5, 0);
    vector<ll> P(n + 5, 0);
    vector<vector<ll>> rmq(n + 5, vector<ll>(18, 0));

    for (int i = 1; i <= n; i++){
        cin >> A[i];
        P[i] = P[i - 1] + A[i];        
        rmq[i][0] = A[i] + P[i];
    }
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);

    vector<vector<int>> add(n + 5), rem(n + 5);

    auto ins = [&](int l, int r, int v){
        l = max(l, 1);

        if (l > r)
            return;

        add[l].push_back(v);
        rem[r + 1].push_back(v);
    };
    for (int r = 1; r <= n; r++){
        // r is a roadblock
        if (A[r] > P[r - 1])
            ins(1, r - 1, r);

        // Find leftmost l possible
        int lowerB = upper_bound(P.begin() + 1, P.begin() + n + 1, P[r - 1] - A[r]) - P.begin();
        int lo = lowerB, hi = r - 1;

        while (lo < hi){
            int mid = (lo + hi) / 2;

            // Query lowerB...mid
            int lg = 31 - __builtin_clz(mid - lowerB + 1);
            ll val = max(rmq[lowerB][lg], rmq[mid - (1 << lg) + 1][lg]);

            val > P[r - 1] ? hi = mid : lo = mid + 1;
        }
        ins(lo + 1, r - 1, r);
    }

    multiset<int> badR{n + 1};
    vector<int> ans(n + 5, 0);
    ll worst = 0; 

    for (int i = 1; i <= n; i++){
        for (int v : add[i])
            badR.insert(v);
        for (int v : rem[i])
            badR.erase(badR.find(v));

        int l = lower_bound(P.begin() + i, P.begin() + n + 1, worst) - P.begin();
        int r = *badR.begin();

        // Active for interval [l...r)
        if (l <= r){
            ans[l]++;
            ans[r]--;
        }
        worst = max(worst, A[i] + P[i]);
    }
    
    for (int i = x; i <= n; i++){
        ans[i] += ans[i - 1];
        cout << ans[i] << " \n"[i == n];
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}