First, sort $$$h_1 \leq h_2 \leq \dots \leq h_{2n}$$$. There is a very explicit description to which $$$h_i$$$'s work.

We have a very explicit description of whether the arrangement is possible. Sort the heights so that $$$h_1 \leq h_2 \leq \dots \leq h_{2n}$$$. Then, there exists such arrangement if and only if all the following conditions hold.

We present two proofs.

Proof 1 (Direct Proof). We will directly show that $$$h_{n+i} - h_i \geq x$$$ for all $$$i$$$.

To do so, note that $$$n+1$$$ people who have height in $$$[h_i, h_{n+i}]$$$ It's impossible that these $$$n+1$$$ people got assigned to different columns (because there are $$$n$$$ columns), so two people got assigned to the same row.

However, the difference of heights between these two people is at most $$$h_{n+i}-h_i$$$, implying that $$$h_{n+i}-h_i\geq x$$$. $$$\blacksquare$$$

Proof 2 (Exchange Argument). First, we look at two pairs. Suppose that the $$$i$$$-th person in the first and second row have heights $$$a < b$$$, while the $$$j$$$-th person in the first and second row have heights $$$c < d$$$.

• Assume that $$$b\geq c$$$, then we switch $$$b,c$$$. The arrangement still works since $$$a-c \geq a-b \geq x$$$ and $$$b-d \geq c-d \geq x$$$.
• Similarly, $$$a\geq d$$$ is yields a switch.

Thus, we can keep exchanging until anyone in the first row is at least as tall as anyone in the second row. Thus, the first row must be $$$h_{n+1}, h_{n+2}, \dots, h_{2n}$$$, while the second row must be $$$h_1, h_2, \dots, h_n$$$ in some order.

Now, we look at the same picture again. Assume that $$$a\geq c$$$ but $$$b\leq d$$$. then, we can switch $$$b,d$$$, and it still works because $$$a-d \geq c-d \geq x$$$ and $$$c-b \geq c-d \geq x$$$. Thus, we can switch the second row until it matches the order of the first row.

Therefore, we force the first row to be $$$h_{n+1}, h_{n+2}, \dots, h_{2n}$$$, while the second row must be $$$h_1, h_2, \dots, h_n$$$ in that order. This implies the conclusion. $$$\blacksquare$$$

Time Complexity: $$$O(n\log n)$$$ for sorting.

#include <bits/stdc++.h>

using namespace std;

void solve(){
	int n, x; cin >> n >> x;
	vector<int> a(2*n);
	for(int i=0; i<2*n; ++i)
		cin >> a[i];
	sort(a.begin(), a.end());
	bool ok = true;
	for(int i=0; i<n; ++i)
		if(a[n+i] - a[i] < x) ok = false;
	cout << (ok ? "YES" : "NO") << "\n";
}

int main(){
	int tt; cin >> tt;
	while(tt--) solve();
}

The optimal way is to fill all the zero entries first.

Delete the leading zeroes in the array $$$a$$$ (i.e., the first $$$t$$$ numbers of $$$a$$$ that are zero) so that now $$$a_1\ne 0$$$. Let $$$k$$$ be the number of $$$0$$$'s in $$$a_1,a_2,\dots,a_{n-1}$$$. The answer is

To see why, let Mark keep filling the holes (rooms with dust level $$$0$$$) first by subtracting the first nonzero index and changing the first zero index to $$$1$$$. This takes $$$k$$$ moves to fill all zeroes in $$$a_1,a_2,\dots,a_{n-1}$$$. Then, we can start moving, from left to right, all dust to the $$$n$$$-th room, taking $$$a_1+a_2+\dots+a_{n-1}$$$ moves.

Finally, we argue that this is the minimum number of moves. To that end, we prove that each move decreases the answer by at most $$$1$$$. We consider two cases.

• If a move has $$$j=n$$$, then it decreases $$$a_1+a_2+\dots+a_{n-1}$$$ by $$$1$$$ but does not decrease $$$k$$$.
• If $$$j\ne n$$$, then the move doesn't decrease $$$a_1+a_2+\dots+a_{n-1}$$$ and decreases $$$k$$$ by at most $$$1$$$.

Thus, we are done. The time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
#define ll long long

using namespace std;


void solve(){
    int n; cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; ++i)
        cin >> a[i];
    ll ans = 0;
    int ptr = 0;
    while(ptr < n && a[ptr] == 0)
        ptr++;
    for(int i=ptr; i<n-1; ++i){
        ans += a[i];
        if(a[i] == 0) ans++;
    }
    cout << ans << "\n";
}
int main(){
    int tt; cin >> tt;
    while(tt--) solve();
}

You can't keep the entire string, but there is an efficient way to track what letter each index comes from.

This is an implementation problem. What you need to do is after the $$$i$$$-th copying operation, we need to keep track of the beginning point $$$a_i$$$ and the ending point $$$b_i$$$ of the appended string. Moreover, we also keep track the subtraction distance $$$t_i = a_i-l_i$$$ so that for $$$k\in [a_i, b_i]$$$, the $$$k$$$-th letter is the same as the $$$(k-t_i)$$$-th letter. Thus, we have recursed the position to the smaller position $$$k-t_i$$$, so we keep doing that until we reach the initial string.

Therefore, to solve this problem, we iterate from $$$i=c,c-1,\dots,1$$$. If $$$k$$$ is in $$$[a_i,b_i]$$$, subtract $$$k$$$ by $$$t_i$$$. After all operations, $$$k$$$ should be at the inital string, and we output the $$$k$$$-th letter.

The time complexity of this solution is $$$O(cq)$$$. However, less efficient solutions of $$$O((c\log c) q)$$$ (using binary search each time) or $$$O(c^2q)$$$ (by going through all intervals in each iteration) pass as well.

#include<bits/stdc++.h>
#define ll long long

using namespace std;

void solve(){
	int n, c, q; cin >> n >> c >> q;
	string s; cin >> s;

	vector<ll> left(c+1), right(c+1), diff(c+1);
	left[0] = 0;
	right[0] = n;

	for(int i=1; i<=c; ++i){
		ll l, r; cin >> l >> r;
		l--; r--;
		left[i] = right[i-1];
		right[i] = left[i] + (r-l+1);
		diff[i] = left[i] - l;
	}
	
	while(q--){
		ll k; cin >> k;
		k--;
		for(int i=c; i>=1; --i){
			if(k < left[i]) continue;
			else k -= diff[i];
		}
		cout << s[k] << "\n";
	}
}

int main(){
	int tt; cin >> tt;
	while(tt--) solve();
}