You have to create a rectangle of arbitrary dimensions with maximum area. You can do it by stacking all blocks vertically on top of each other, which gives a rectangle of dimension $$$1$$$ x $$$\sum_{i=1}^{n}{a_i}$$$.

Time Complexity: $$$O(n)$$$

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n; cin >> n;
	ll ans = 0;
	while(n --) {
		ll x; cin >> x;
		ans += x;
	}
	cout << ans;
 
	return 0;
}

There are several ways to solve this problem, one of which is mentioned here. Let $$$x$$$ be the number after dividing $$$a[0]$$$ by 2 until we get an odd number. Now if all the remaining elements are in the form $$$x{2^k}$$$, where $$$k$$$ is some arbitrary number, then our answer exists. Now it is easy to check whether the remaining elements are in the form $$$x{2^k}$$$, just divide $$${a_i}$$$ by $$$x$$$ and check for the quotient whether it is of the form $$${2^k}$$$ or not.

Time Complexity: $$$O(n \log n)$$$ or $$$O(n)$$$ depending on your implementation

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAX = 1e5 + 10;
ll a[MAX];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n; cin >> n;
	set <ll> pw;
	ll cur = 1;
	while(cur <= INF) {
		pw.insert(cur);
		cur <<= 1;
	}
	ll g = 0;
	for(int i = 0; i < n; i ++) {
		cin >> a[i];
		g = __gcd(g, a[i]);
	}
	bool flag = false;
	for(int i = 0; i < n; i ++) {
		ll tmp = a[i] / g;
		flag |= (pw.find(tmp) == pw.end());
	}
	cout << (!flag ? "YES" : "NO");
	
	return 0;
}

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

#define endl '\n'
#define all(v) v.begin(), v.end()
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(0);  cin.tie(NULL);  cout.tie(NULL);
	int n;		
	cin>>n;
	vector<ll> arr(n);
	for(auto &x: arr)	cin>>x;
	ll x = arr[0];
	
	while(x % 2 == 0)
		x /= 2;
	bool exist = true;
	
	for(int i = 1; i < n; i++) {
		if(arr[i] % x != 0) {
			exist = false;
			break;
		}
		ll y = arr[i] / x;
		if((y&(y-1)) != 0)
			exist = false;
	}
	
	if(exist)	cout<<"Yes"<<endl;
	else 		cout<<"No"<<endl;
	return 0;
}

Here $$$k \le {10^5}$$$, so for each coin we can upgrade the pipe with minimum capacity with it's corresponding $$${x_i}$$$. We can use set<pair<long long, int>> to obtain pipe with minimum capacity and update it.

Time Complexity: $$$O(k \log n)$$$

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int MAX = 1e5 + 10;
ll n, k;
ll c[MAX], x[MAX];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	for(int i = 1; i <= n; i ++) cin >> c[i] >> x[i];
	set <pair <ll, int>> s;
	for(int i = 1; i <= n; i ++) s.insert({c[i], i});
	while(k --) {
		auto p = *s.begin();
		s.erase(s.begin());
		ll curcap = p.first, id = p.second;
		s.insert({curcap + x[id], id});
	}
	cout << (*s.begin()).first;
	
	return 0;
}

Unlike the easy version, we cannot iterate for each coin as $$$k \le {10^9}$$$. Instead, we can use binary search to obtain the maximum flow. First, let us assume $$$x$$$ to be the maximum flow, now we can check if we can achieve this flow using at most $$$k$$$ coins. If $$$x$$$ can be achieved then $$$x$$$ is our answer and we look for a bigger $$$x$$$, otherwise we look for a smaller $$$x$$$.

NOTE: Since answer can be bigger than $$$10^{18}$$$, it is better to use upper bound as $$$2 \cdot 10^{18}$$$.

Time Complexity: $$$O(n \log ({2 \cdot 10^{18}}))$$$

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int MAX = 1e5 + 10;
ll n, k, c[MAX], x[MAX];
bool f(ll val) {
	ll cost = 0;
	for(int i = 1; i <= n; i ++) {
		if(c[i] >= val) continue;
		ll diff = val - c[i];
		cost += diff / x[i];
		if(diff % x[i] != 0) cost ++;
		if(cost > k) return false;
	}
	return cost <= k;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	for(int i = 1; i <= n; i ++) cin >> c[i] >> x[i];
	ll l = 0, r = 2e18;
	while(r - l > 1) {
		ll m = (l + r) / 2;
		if(f(m)) l = m;
		else r = m;
	}
	cout << l;
	
	return 0;
}

Consider an example $$$mmeeooww$$$, here every letter is repeated 2 times. Here we can form a total of 18 good strings. How are we calculating the number of good strings? Let's see.

First observation: Number of picked $$$m$$$ and $$$w$$$ do not affect good string. So we first calculate total number of ways to pick non-zero number of $$$m$$$, which is equal to $$$({2^{n_m}}-1)$$$, similarly for $$$w$$$ the number of ways are $$$({2^{n_w}}-1)$$$.

Second Observation: We cannot pick only one $$$e$$$. Because then after we cannot pick any $$$o$$$ as $$$n_e > n_o$$$ must hold. So let's pick $$$k$$$ number of $$$e's$$$, so good strings can have $$${1, 2 \dots k-1}$$$ numbers of $$$o$$$. Picking $$$1$$$ $$$o$$$ from $$$n_o$$$ number of $$$o's$$$ is $$$\binom{n_o}{1}$$$, for $$$2$$$ is $$$\binom{n_o}{2}$$$ $$$\dots$$$ for $$$k-1$$$ is $$$\binom{n_o}{k-1}$$$. We can precompute each binomail coefficient. Now answer for $$$k$$$ number of $$$e$$$ is $$$({2^{n_m}}-1) \space \binom{n_e}{k} \space (\sum_{x=1}^{k-1} \binom{n_o}{x}) \space ({2^{n_w}}-1)$$$. We can do this for each $$$k$$$ from 2 to $$${n_e}$$$.

Time Complexity: $$$O(n)$$$

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

#define endl '\n'
#define all(v) v.begin(), v.end()
typedef long long ll;

const ll mod = 1e9 + 7;

ll power(ll x, ll y) {
    ll res = 1;
    while(y) {
        if (y & 1)  res = (res*x) % mod;
        y >>= 1;
        x = (x*x) % mod;
    }
    return res;
}

vector<ll> fact;

void preprocess(int n) {
    fact.resize(n+1, 1);
    for(int i = 2; i <= n; i++)
        fact[i] = (fact[i-1] * i) % mod;
    return;
}

ll nCr(ll n, ll r) {
    return fact[n] * power(fact[r], mod-2) % mod * power(fact[n-r], mod-2) % mod;
}

int main() {
	int n;		cin>>n;
	string s;	cin>>s;
	
	int n_m = count(all(s), 'm');
	int n_e = count(all(s), 'e');
	int n_o = count(all(s), 'o');
	int n_w = count(all(s), 'w');

	if(n_m == 0 or n_e == 0 or n_o == 0 or n_w == 0) {
		cout << 0 << endl;
		exit(0);
	}
	
	preprocess(n);
	
	ll tot_ways_m = 1, tot_ways_w = 1;
	for(int i = 1; i <= n_m; ++i)
		tot_ways_m = (tot_ways_m << 1) % mod;
	tot_ways_m = (mod + tot_ways_m - 1) % mod;
	
	for(int i = 1; i <= n_w; ++i)
		tot_ways_w = (tot_ways_w << 1) % mod;
	tot_ways_w = (mod + tot_ways_w - 1) % mod;

	vector<ll> ncr(n + 1);
	for(int i = 1; i <= n_o; ++i)
		ncr[i] = nCr(n_o, i);
	for(int i = 1; i <= n_e; ++i)
		ncr[i] = (ncr[i] + ncr[i-1]) % mod;

	ll ans = 0;

	for(int i = 2; i <= n_e; ++i) {
		ll temp = 1;
		temp = temp * tot_ways_m % mod;
		temp = temp * nCr(n_e, i) % mod;
		temp = temp * ncr[i-1] % mod;
		temp = temp * tot_ways_w % mod;
		ans = (ans + temp) % mod;
	}

	cout << ans << endl;
}

Initially, there were two subtasks for this problem. In the first task, you need to find a valid numbering for a given tree and in second subtask you need to validate for a given tree and numbering if it is optimal or not. The first subtask was just a modified version of problem 1325C so I decided to remove it.

Let the maximum value of $$$MEX(u, v)$$$ be $$$x$$$. The most important observation for this problem is that we put numbers $$$0,1,2 \dots x-1$$$ on a path which is longest among all the paths. This path is known as $$$diameter$$$ and is easy to find. Now we have to check if values $$$0,1,2 \dots x-1$$$ lie on a diameter. How can we do that? Let's create a new graph $$$G$$$ using the edges with numbers $$$0,1,2 \dots x-1$$$, we know if the numbering is optimal, these edges form a line graph. We can check if $$$G$$$ is a line graph and that will be the answer.

Time Complexity: $$$O(n)$$$

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int MAX = 1e5 + 10;
vector <int> g[MAX];
bool vis[MAX];
int x[MAX], d[MAX], U[MAX], V[MAX];
void dfs(int u, int p = 0) {
	for(int v : g[u]) {
		if(v != p) {
			d[v] = d[u] + 1;
			dfs(v, u);
		}
	}
}
void dfs1(int u) {
	vis[u] = true;
	for(int v : g[u]) if(!vis[v]) dfs1(v);
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n; cin >> n;
	set <int> used;
	for(int i = 1; i < n; i ++) {
		cin >> U[i] >> V[i] >> x[i];
		used.insert(x[i]);
		g[U[i]].push_back(V[i]);
		g[V[i]].push_back(U[i]);
	}
	if((int) used.size() != n - 1) return cout << "No", 0;
	dfs(1);
	int a = max_element(d, d + MAX) - d;
	memset(d, 0, sizeof(d));
	dfs(a);
	int dim = *max_element(d, d + MAX);
	for(int i = 1; i <= n; i ++) g[i].clear();
	for(int i = 1; i < n; i ++) {
		if(x[i] < dim) {
			g[U[i]].push_back(V[i]);
			g[V[i]].push_back(U[i]);
		}
	}
	int comp = 0, one = 0, two = 0;
	for(int i = 1; i <= n; i ++) {
		int deg = g[i].size();
		if(deg == 0) continue;
		if(deg == 1) one ++;
		else if(deg == 2) two ++;
		else return cout << "No", 0;
		if(!vis[i]) {
			dfs1(i);
			comp ++;
		}
	}
	if(one == 2 && two == dim - 1 && comp == 1) cout << "Yes";
	else cout << "No";
	
	return 0;
}

Since the array $$$p$$$ is a static array and the queries may overlap with each other, we can use Mo's Algorithm to solve this problem. When adding an element $$$x$$$, we add to our answer the number of elements in range $$$[0, x-k]$$$ and $$$[x+k, 10^6]$$$. When removing an element $$$x$$$, we subtract from out answer the number of elements in range $$$[0, x-k]$$$ and $$$[x+k, 10^6]$$$. To find number of element in these ranges, we can use Fenwick Tree.

Time Complexity: $$$O((n+q)\sqrt{n} \log ({10^6}))$$$

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int BLK = 900;
const int MAX = 1e5 + 10;
const int MAXV = 1e6 + 10;
int n, k, q, p[MAX];
struct Query {
	int l, r, id;
	void read(int _i) {
		cin >> l >> r;
		id = _i;
	}
	bool operator < (Query a) {
		if(l / BLK != a.l / BLK) return l / BLK < a.l / BLK;
		return ((l / BLK) & 1 ? r < a.r : r > a.r);
	}
} Q[MAX];
ll ans[MAX], cur = 0;
struct FenwickTree {
	int n;
	vector <int> BIT;
	FenwickTree(int n):
		n(n), BIT(2 * n) {}
	void update(int x, int val) {
		while(x <= n) {
			BIT[x] += val;
			x += x & (-x);
		}
	}
	int get(int x) {
		int sum = 0;
		while(x > 0) {
			sum += BIT[x];
			x -= x & (-x);
		}
		return sum;
	}
};
FenwickTree FW(MAXV + 100);
int query(int l, int r) {
	if(l < 2) return FW.get(r);
	return FW.get(r) - FW.get(l - 1);
}
void add(int x) {
	cur += query(0, x - k) + query(min(x + k, MAXV), MAXV);
	FW.update(x, 1);
}
void remove(int x) {
	cur -= query(0, x - k) + query(min(x + k, MAXV), MAXV);
	FW.update(x, -1);
}
void mos_algorithm() {
	int l = Q[0].l, r = Q[0].l - 1;
	for(int i = 0; i < q; i ++) {
		while(l < Q[i].l) remove(p[l ++]);
		while(l > Q[i].l) add(p[-- l]);
		while(r < Q[i].r) add(p[++ r]);
		while(r > Q[i].r) remove(p[r --]);
		ans[Q[i].id] = cur;
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> q >> k;
	for(int i = 1; i <= n; i ++) cin >> p[i];
	for(int i = 0; i < q; i ++) Q[i].read(i);
	sort(Q, Q + q);
	mos_algorithm();
	for(int i = 0; i < q; i ++) cout << ans[i] << "\n";
	
	return 0;
}