There are many ways to solve this problem. One of which is described here.

All we have to do is find the maximum number of indices such that both strings have different values. We can do this by sorting one string in increasing order and another one in decreasing order. Now count of these indices gives us the number of set bits and the remaining are unset bits.

Time Complexity: $$$O(n \log 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);
	
	string s, t;
	cin >> s >> t;
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	reverse(t.begin(), t.end());
	string ans = "";
	for(int i = 0; i < (int) s.size(); i ++) {
		if(s[i] != t[i]) ans += "1";
		else ans += "0";
	}
	sort(ans.begin(), ans.end());
	reverse(ans.begin(), ans.end());
	cout << ans;
	
	return 0;
}

Go for the tutorial of GS more like BS(Hard version)

Unlike in Kadane's Algorithm, we set our max_ending_here variable to zero if and only if we are at a good index and max_ending_here is less than zero.

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;
        vector<int> arr(n), g(n);
        for(int i = 0; i < n; i ++)  cin >> arr[i];
        for(int i = 0; i < n; i ++)  cin >> g[i];
        ll max_sum_so_far = 0, max_sum = -2e18, st = -1;
        for(int i = 0; i < n; i ++) {
      	    if(g[i] == 1)	st = 1;
            if(g[i] == 1 and max_sum_so_far < 0)
                max_sum_so_far = 0;
            if(st == -1)	continue;
            max_sum_so_far += arr[i];
            max_sum = max(max_sum, max_sum_so_far);
        }
        cout << max_sum << endl;
	return 0;
}

Let us assume that the first person is the one with the lowest skills. Now we iterate through all other applicants to check whether someone has skills less than the assumed one, if yes we change our person to this one, and do the same for remaining. Now, at last, we have a profile with the lowest skills. Let the index of this profile is $$$x$$$. Now we check if there is someone who has fewer skills than the person with a profile index $$$x$$$. If it exists then the answer is straightforward $$$-1$$$, else $$$x$$$ is the answer.

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

Let's say we know, there exists a lusar index at position $$$P$$$. Now If we start comparing the element from position 1 to $$$P-1$$$ and have current lusar index $$$Q$$$. $$$P$$$-th student will lose against $$$Q$$$ , making current lusar id into $$$P$$$. Nobody will lose against $$$P$$$ after that, resulting in $$$P$$$ being our final answer. (Because we know that it is our lusar element).

What if there is No lusar element? Why do we require verification for the lusar element again from the start?

Well! That's because the comparator here is not transitive. If $$$a$$$ lost to $$$b$$$ and $$$b$$$ lost to $$$c$$$ that does not imply that $$$a$$$ will lose to $$$c$$$. But If $$$c$$$ loses to $$$a$$$ here that makes one thing certain that there is no ultimate lusar between $$$a$$$,$$$b$$$, and $$$c$$$.

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

struct student {
    int a, b, c;
};
bool operator<(const student& t, const student& o)
{
    int cntLess = 0;
    if (t.a < o.a)
        cntLess++;
    if (t.b < o.b)
        cntLess++;
    if (t.c < o.c)
        cntLess++;
    return cntLess >= 2;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<student> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].a >> v[i].b >> v[i].c;
    }
    int id = 0;
    for (int i = 1; i < n; ++i) {
        if (v[i] < v[id]) {
            id = i;
        }
    }
    for (int i = 0; i < n; i++) {
        if (i == id)
            continue;
        if (v[i] < v[id]) {
            cout << -1 << '\n';
            return 0;
        }
    }
    cout << id + 1 << '\n';
}

This problem can be solved using a linked-list. We can maintain a linked-list L that represents our queue currently. To handle a query of type:

1. Serve: Delete the node at the head position of the linked list.

2. Insert X Y: If we have the address of the node containing Y somewhere. We can insert a new node containing X right after Y.(See the solution for insight.)

3. Mafia X: Insert the node at the beginning of the linked list.

To store the address of the node containing string S, We can maintain a map/hashmap.

Time Complexity: $$$O(N + M \log(N)))$$$

#include "bits/stdc++.h"
using namespace std;
struct node {
    string data;
    struct node* next = NULL;
    node(string data_)
    {
        data = data_;
    }
}* head = NULL;

map<string, node*> mp;

void insert_begin(string data)
{
    //       (head,data)--->....
    //
    // (temp,data)
    node* temp = new node(data);
    mp[data] = temp;

    temp->next = head;
    //       head--->
    //		/
    // (temp)

    // temp is the new head from now on.
    head = temp;
}
void delete_begin()
{
    if (head != NULL) {
        mp.erase(head->data); // erase 1st node from map
        node* new_head = head->next; // new head will be 2nd node
        free(head); // free head memory head is null now
        head = new_head; // set head = newhead
    }
}
void insert_after(string X, string Y)
{
    node* newnode = new node(X);
    mp[X] = newnode;
    //    made (X-->NULL)

    //-- Y---Z --
    // went to node Y.
    node* temp = mp[Y];

    // set x->next = y->next
    //-- Y---Z --
    //	    /
    //	   X
    newnode->next = temp->next;

    // set y->next = x and we are done.
    //-- Y   Z --       ===>   --Y--X--Z--
    //	  \/
    //	   X
    temp->next = newnode;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string x[n];
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    for (int i = n - 1; i >= 0; i--) {
        insert_begin(x[i]);
    }
    int q;
    cin >> q;
    string query, X, Y;

    for (int i = 0; i < q; ++i) {
        cin >> query;
        if (query[0] == 's') {
            delete_begin(); // O(1)
        } else if (query[0] == 'i') {
            cin >> X >> Y;
            insert_after(X, Y); // O(1)
        } else {
            cin >> X;
            insert_begin(X); // O(1)
        }
    }
    while (head) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

We are given a forest i.e. arbitrary number of trees. All we have to do is find the diameter of all the small trees and if there are $$$x$$$ numbers of trees. Then the answer is sum of all mini diameters and $$$x-1$$$. ($$$x-1$$$ because we need x-1 edges to join all $$$x$$$ small trees).

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

#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
vector<int> g[N], height(N), vis(N), subtree;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = 0, connected_components = 0;

    function<void(int, int)> dfs = [&](int v, int p) -> void {
        vis[v] = 1;
        subtree.push_back(v);
        for (int u : g[v]) {
            if (u != p) {
                height[u] = height[v] + 1;
                dfs(u, v);
            }
        }
    };

    function<int(int)> find_diameter = [&](int v) -> int {
        subtree.clear();
        dfs(v, -1);
        int ls = v; // most distant node from v.
        for (int u : subtree) {
            if (height[u] > height[ls])
                ls = u;
        }
        height[ls] = 0; // new source for dfs.
        subtree.clear();
        dfs(ls, -1);
        int mx = 0; // the maximum distance from ls that will be our final answer for diameter.
        for (int u : subtree)
            mx = max(mx, height[u]);
        return mx;
    };

    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            ans += find_diameter(i);
            connected_components++;
        }
    }
    ans = ans + connected_components - 1;
    cout << ans;
}

Let we are on element $$$x$$$, we must add this element to a sequence ending with element ranging from $$$0$$$ to $$$x-1$$$, and have the maximum sum. We can do this by using a segment/Fenwick tree. And store all the elements with their corresponding maximum sum in a map.

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

#include "bits/stdc++.h"
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
#define int long long
int bit[N], n, a[N], m;
void update(int idx, int val, int n)
{
    while (idx <= n) {
        bit[idx] = max(bit[idx], val);
        idx += (idx & -idx);
    }
}
int query(int idx)
{
    int sum = 0;
    while (idx > 0) {
        sum = max(sum, bit[idx]);
        idx -= (idx & -idx);
    }
    return sum;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    scanf("%lld", &n);
    map<int, int> ord;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        ord[a[i]] = 0;
    }
    for (auto i : ord)
        ord[i.first] = ++m;

    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int ansh = query(ord[a[i]] - 1) + a[i];
        update(ord[a[i]], ansh, m);
        mp[a[i]] = max(mp[a[i]], ansh);
    }
    cout << query(m) << " ";
    int res = 0;
    for (auto [x, y] : mp) {
        res += (x % MOD * (y % MOD)) % MOD;
        if (res >= MOD)
            res %= MOD;
    }
    cout << res << endl;
}

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;
}