We need

so it suffices to count the number of inversions in the exit array $$$X$$$ and multiply by two mod $$$10^9 + 7$$$.

There exists a standard way to count inversions in the array using Merge Sort Algorithm.

You can also implement this with a GNU PBDS ordered_set (or equivalently a Fenwick tree).

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

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
typedef tree<
    int, null_type, less<int>, rb_tree_tag,
    tree_order_statistics_node_update
> ordered_set;
using ll = long long;
const ll MOD = 1000000007;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<int> E(n), X(n);
    for(int i=0;i<n;i++) cin>>E[i]; // ignored
    for(int i=0;i<n;i++) cin>>X[i];
 
    ordered_set os;
    ll invCount = 0;
    for(int i=0;i<n;i++){
        int x = X[i];
        ll lessOrEqual = os.order_of_key(x+1);
        ll greaterCount = os.size() - lessOrEqual;
        invCount += greaterCount;
        os.insert(x);
    }
    ll answer = (2 * (invCount % MOD)) % MOD;
    cout << answer << "\n";
    return 0;
}

Apply Mo’s algorithm with block size $$$\lfloor \sqrt{n}\rfloor$$$ to process all queries in $$$O((n+q)\,\sqrt{n}\,\log n)$$$.

Maintain for the current subarray:

• freq[x]: frequency of Pokémon ID $$$x$$$

• st: set of missing non‑negative integers

• st2: set of present integers

• multi: count of integers with freq[x] > 1

For each query:

• if (multi > 0), We have at least one number that appears twice. So we can replace one of its occurrences with the second missing number and thus the answer is third missing number.

auto it = st.begin(); //first missing, ignore it   
it++;  //second missing    
it++;  //third missing    
int val = *it;   
ans[q.idx] = val;   

• else if (multi == 0), there are no repeated elements in the subarray so every element's frequency is $$$1$$$. In order to maximise the MEX (2nd missing), we will always try to replace the maximum element of the current window. It is easy to see that this is the most optimal strategy. Let mex2 be the 2nd missing number and mx be the maximum element.
  • Case $$$1$$$ : mex2 > mx, there is no need to change the mx element and our answer will simply be mex2.
  • Case $$$2$$$ : mex2 <= mx, we will replace (hypothetically) the mx element with mex2, thus our new second missing element will be the minimum of mx and mex3 (3rd missing).

auto it = st.begin();
it++;
int mex2 = *it; // 2nd missing element
int mx = *st2.rbegin(); //maximum present element
if(mex2 > mx){
    ans[q.idx] = mex2;
}
else{
    it++;  
    int mex3 = *it; // 3rd missing element
    mex3 = min(mex3,mx); 
    ans[q.idx] = mex3;
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define pb push_back
 
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
const int MAXN = 1e5+6;
vector<int> freq(MAXN);
set<int> st;
set<int> st2;
int block_size;
 
int sqt(int n){
    int l = 1;
    int r = 1;
    while(r*r <= n){
        r *= 2;
    }
    int ans = 0;
    while(l <= r){
        int mid = l + (r-l)/2;
        if(mid*mid == n){
            return mid;
        }
        else if(mid*mid < n){
            ans = mid;
            l = mid+1;
        }
        else{
            r = mid-1;
        }
    }
    return ans;
}
 
struct Query {
    int l, r, idx;
    bool operator<(const Query &other) const {
        if (l / block_size != other.l / block_size)
            return l / block_size < other.l / block_size;
        return (l / block_size & 1) ? (r < other.r) : (r > other.r);
    }
};
 
 
vector<int> mosAlgo(vector<int>& v, vector<Query>& queries){
    int n = v.size();
    int q = queries.size();
    block_size = sqt(n);
    sort(queries.begin(),queries.end());
 
    for(int i = 0; i <= n+5; i++){
        freq[i] = 0;
        st.insert(i);
    }
 
    vector<int> ans(q);
 
    int curL=0, curR = -1;
    int multi=0;
 
    auto add = [&](int pos){
        int val = v[pos];
        freq[val]++;
        if(freq[val]==1){
            st.erase(val);
            st2.insert(val);
        }
        else if(freq[val]==2){
            multi++;
        }
 
    };
 
    auto remove = [&](int pos){
        int val = v[pos];
        freq[val]--;
        if(freq[val]==0){
            st.insert(val);
            st2.erase(val);
        }
        else if(freq[val]==1){
            multi--;
        }
 
    };
 
    for(Query q: queries){
        while(curL < q.l){
            remove(curL++);
        }
        while(curL > q.l){
            add(--curL);
        }
        while(curR < q.r){
            add(++curR);
        }
        while(curR > q.r){
            remove(curR--);
        }  
 
        if(multi==0){
            auto it = st.begin();
            it++;
            int mex2 = *it; 
            int mx = *st2.rbegin(); 
            if(mex2 > mx){
                ans[q.idx] = mex2;
            }
            else{
                it++;  
                int mex3 = *it; 
                mex3 = min(mex3,mx); 
                ans[q.idx] = mex3;
            }
        }
        else{
            auto it = st.begin();
            it++;
            it++;
            int val = *it;
            ans[q.idx] = val;        
        }
    }
    return ans;
 
}
 
void solve(){
    int n,q;
    cin>>n>>q;
    st.clear();
    st2.clear();
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
 
    vector<Query> queries(q);
    for(int i=0;i<q;i++){
        cin>>queries[i].l >> queries[i].r;
        queries[i].l--;
        queries[i].r--;
        queries[i].idx = i;
    }
 
    vector<int> ans = mosAlgo(v,queries);
    for(auto i:ans){
        cout<<i<<endl;
    }
 
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
 

For a perfect $$$b$$$-ary tree of height $$$h$$$, when $$$b=1$$$, the tree degenerates into a single chain. In this case, we can choose the entire chain as the Golden Path, yielding a total distance of $$$0$$$.

However, when $$$b \gt 1$$$, by symmetry, the optimal Golden Path is any leaf-to-root-to-leaf path. We can pick one such path and compute the contribution of all the nodes not on this path to the total distance.

1. Off-path siblings at the same level.
   The path-node at depth $$$i$$$ has $$$b$$$ children (one continues the path, one is its parent), leaving $$$(b-2)$$$ siblings each hanging a trivial subtree of height $$$0$$$. Factoring out the overall $$$b^i$$$ identical branches and the distance-multiplier $$$i$$$ yields a contribution

1. Full side-subtrees of height $$$(h - i)$$$.
   The remaining $$$(b-1)$$$ children each root a perfect $$$b$$$-ary subtree of height $$$h-i$$$. Its total distance sum is

which, when multiplied by $$$(b-1)$$$ subtrees and simplified, contributes

Combining both parts, the total contribution at level $$$i$$$ is

times the common factor

Hence each iteration adds

to the running sum, and we update

by multiplying by $$$b$$$. Summing over $$$i=1$$$ to $$$h$$$ yields the minimum total distance.

Time Complexity

• We perform a single loop from $$$i = 1$$$ to $$$i = h$$$, computing and updating values in constant time per iteration.
• Therefore, the overall time complexity is:

• The space complexity is $$$\mathcal{O}(1)$$$ as we only use a few variables.

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
int MOD = 1e9 + 7;
 
 
void solve(){
    int height,b;
    cin>>b>>height;
    if(b==1){
        cout<<0<<endl;
        return;
    }
    int ans = 0;
    int powd = 1;
    for(int i=1;i<=height;i++){
        int term1 = (((b-2) % MOD + (((b-1) % MOD * ((height-i) % MOD)) % MOD * 2 % MOD)) % MOD);
        int term2 = ((powd % MOD) * (i % MOD)) % MOD;
        ans = (ans + (term1 * term2) % MOD) % MOD;
        powd = (powd * b) % MOD;
    }
    cout<<ans<<endl;
}
 
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Only palindromes of length 2 $$$(a[i] = a[i+1])$$$ and length 3 $$$(a[i] = a[i+2] ≠ a[i+1])$$$ matter. If we can track these, we can implicitly track all longer palindromes as well.

We maintain a set of “bad” markers at positions $$$(i, i+1)$$$ or $$$(i, i+2)$$$, indicating the presence of such palindromes.

Let the sorted markers be:

Then, valid subarrays lie entirely within the gaps:

A gap of length $$$L$$$ contributes: $$$\frac{L\times(L+1)}{2}$$$ valid subarrays.

However, there may be duplicates. Specifically, each length-3 marker contributes exactly one duplicate, so we always subtract 1 for each length-3 marker. The "why" part is simple and is left as an exercise for the reader

We can efficiently process range updates using a segment tree.

For each update on range [l..r], we only need to check the following six segments for possible changes, namely:

• $$${(l−2) ... (l)}$$$
• $$${(l−1)...(l+1)}$$$
• $$${(r−1)...(r+1)}$$$
• $$${(r)...(r+2)}$$$
• $$${(l−1)... (l)}$$$
• $$${(r)...(r+1)}$$$

We can update the answer based on insertions and deletions, for implementation details, please check the embedded code below.

• Time Complexity: $$$O((n + Q) \log n)$$$
• Memory Usage: $$$O(n)$$$

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
class SegmentTree {
private:
    int n;
    vector<int> seg, lazy;
 
    void pushDown(int idx, int start, int end) {
        if (lazy[idx] != 0) {
            seg[idx] += (end - start + 1) * lazy[idx];
            if (start != end) {
                lazy[idx * 2] += lazy[idx];
                lazy[idx * 2 + 1] += lazy[idx];
            }
            lazy[idx] = 0;
        }
    }
 
    void updateRange(int idx, int start, int end, int l, int r, int val) {
        pushDown(idx, start, end);
        if (start > r || end < l) return;
        if (l <= start && end <= r) {
            lazy[idx] += val;
            pushDown(idx, start, end);
            return;
        }
        int mid = (start + end) >> 1;
        updateRange(idx * 2, start, mid, l, r, val);
        updateRange(idx * 2 + 1, mid + 1, end, l, r, val);
        seg[idx] = seg[idx * 2] + seg[idx * 2 + 1];
    }
 
    int queryPoint(int idx, int start, int end, int pos) {
        pushDown(idx, start, end);
        if (start == end) return seg[idx];
        int mid = (start + end) >> 1;
        if (pos <= mid) return queryPoint(idx * 2, start, mid, pos);
        else return queryPoint(idx * 2 + 1, mid + 1, end, pos);
    }
 
public:
    SegmentTree(int n) : n(n) {
        seg.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
    }
 
    void update(int l, int r, int val) {
        updateRange(1, 1, n, l, r, val);
    }
 
    int query(int pos) {
        return queryPoint(1, 1, n, pos);
    }
};
 
inline int triangular(int x) {
    return x * (x + 1) / 2;
}
 
void updateAnswer(set<pair<int, int>>& palindromes, pair<int, int> marker, 
                 bool isInserting, int& answer, int n) {
    if (marker.second - marker.first == 2) {
        answer += isInserting ? -1 : 1;
    }
 
    auto it = palindromes.find(marker);
 
    if (!isInserting) {
        auto before = it;
        auto after = next(it);
        bool isFirst = (it == palindromes.begin());
        bool isLast = (after == palindromes.end());
 
        auto curr = *it;
 
        if (isFirst) {
            if (isLast) {
                answer = triangular(n);
            } else {
                auto afterVal = *after;
                answer -= triangular(curr.second - 1);
                answer -= triangular(afterVal.second - 1 - curr.first);
                answer += triangular(afterVal.second - 1);
            }
        } else {
            before--;  
            auto beforeVal = *before;
 
            if (isLast) {
                answer -= triangular(n - curr.first);
                answer -= triangular(curr.second - 1 - beforeVal.first);
                answer += triangular(n - beforeVal.first);
            } else {
                auto afterVal = *after;
                answer -= triangular(curr.second - 1 - beforeVal.first);
                answer -= triangular(afterVal.second - 1 - curr.first);
                answer += triangular(afterVal.second - 1 - beforeVal.first);
            }
        }
 
        palindromes.erase(it);
    } else {
        palindromes.insert(marker);
        it = palindromes.find(marker);
        auto curr = *it;
 
        bool isFirst = (it == palindromes.begin());
        auto after = next(it);
        bool isLast = (after == palindromes.end());
 
        if (isFirst) {
            if (isLast) {
                answer -= triangular(n);
                answer += triangular(curr.second - 1);
                answer += triangular(n - curr.first);
            } else {
                auto afterVal = *after;
                answer += triangular(curr.second - 1);
                answer += triangular(afterVal.second - 1 - curr.first);
                answer -= triangular(afterVal.second - 1);
            }
        } else {
            auto before = prev(it);
            auto beforeVal = *before;
 
            if (isLast) {
                answer += triangular(n - curr.first);
                answer += triangular(curr.second - 1 - beforeVal.first);
                answer -= triangular(n - beforeVal.first);
            } else {
                auto afterVal = *after;
                answer += triangular(curr.second - 1 - beforeVal.first);
                answer += triangular(afterVal.second - 1 - curr.first);
                answer -= triangular(afterVal.second - 1 - beforeVal.first);
            }
        }
    }
}
 
void checkPalindromes(int pos, int n, SegmentTree& st, set<pair<int, int>>& palindromes, 
                     set<pair<int, int>>& toRemove, set<pair<int, int>>& toAdd) {
    if (pos <= n-1) {
        bool isPalindrome = (st.query(pos) == st.query(pos+1));
        bool inSet = (palindromes.find({pos, pos+1}) != palindromes.end());
 
        if (isPalindrome && !inSet) {
            toAdd.insert({pos, pos+1});
        } else if (!isPalindrome && inSet) {
            toRemove.insert({pos, pos+1});
        }
    }
 
    if (pos <= n-2) {
        bool isPalindrome = (st.query(pos) == st.query(pos+2) && 
                             st.query(pos) != st.query(pos+1));
        bool inSet = (palindromes.find({pos, pos+2}) != palindromes.end());
 
        if (isPalindrome && !inSet) {
            toAdd.insert({pos, pos+2});
        } else if (!isPalindrome && inSet) {
            toRemove.insert({pos, pos+2});
        }
    }
}
 
void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
 
    SegmentTree st(n+1);
    for (int i = 1; i <= n; i++) {
        st.update(i, i, a[i-1]);
    }
 
    set<pair<int, int>> palindromes;
 
    for (int i = 1; i <= n; i++) {
        if (i <= n-1 && st.query(i) == st.query(i+1)) {
            palindromes.insert({i, i+1});
        }
        else if (i <= n-2 && st.query(i) == st.query(i+2) && st.query(i) != st.query(i+1)) {
            palindromes.insert({i, i+2});
        }
    }
 
    int answer = 0;
    if (palindromes.empty()) {
        answer = triangular(n);
    } else {
        int prevEnd = 0;
        for (auto it = palindromes.begin(); it != palindromes.end(); it++) {
            if (it == palindromes.begin()) {
                answer += triangular(it->second - 1);
            } else {
                auto prevIt = prev(it);
                answer += triangular(it->second - 1 - prevIt->first);
            }
 
            if (it->second - it->first == 2) answer--;
 
            prevEnd = it->first;
        }
 
        if (!palindromes.empty()) {
            auto last = palindromes.rbegin();
            answer += triangular(n - last->first);
        }
    }
 
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        st.update(l, r, x);
 
        set<pair<int, int>> toRemove, toAdd;
 
        for (int i = max(l-2, 1LL); i <= min(l+2, n); i++) {
            checkPalindromes(i, n, st, palindromes, toRemove, toAdd);
        }
 
        for (int i = max(r-2, 1LL); i <= min(r+2, n); i++) {
            checkPalindromes(i, n, st, palindromes, toRemove, toAdd);
        }
 
        for (const auto& marker : toRemove) {
            updateAnswer(palindromes, marker, false, answer, n);
        }
 
        for (const auto& marker : toAdd) {
            updateAnswer(palindromes, marker, true, answer, n);
        }
 
        cout << answer << endl;
    }
}
 
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
 
    while (t--) {
        solve();
    }
    return 0;
}

We have a binary string A (libraryKey) of length m, and for each book i, a binary string bookCodes[i] of length n (which may vary per book). Our goal is to compute the sum of mismatch scores (discount) between A and every contiguous substring of bookCodes[i] of length m, then subtract that discount from the book’s original price. If m > n, the discount for that book is 0.

For a given book j, let B = bookCodes[j] be its code, and A the library key.
By careful observation, we can say that:

For each position i in A (1 ≤ i ≤ m), compare A[i] to every aligned bit in B:

• If A[i] = 0, each ‘1’ in that range adds 1 to the discount.
• If A[i] = 1, each ‘0’ in that range adds 1 to the discount.

Summing these counts over all i gives the total discount for B. We then compute:

finalPrice = max(0, originalPrice — discount)

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
int fun(string a, string b) {
    int n = a.length(), m = b.length();
    if (m < n) return 0;
    vector<vector<int>> ve(m);
    int z = 0, o = 0;
    for (int i = 0; i < m; i++) {
        if (b[i] == '1') o++;
        else z++;
        ve[i] = {z, o};
    }
 
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int lastind = m - (n - i);
        if (a[i] == '1') {
            ans += ve[lastind][0];
            if (i > 0) ans -= ve[i - 1][0];
        } else {
            ans += ve[lastind][1];
            if (i > 0) ans -= ve[i - 1][1];
        }
    }
    return ans;
}
 
void solve() {
    string s;
    cin >> s;
    int n;
    cin >> n;
    vector<string> ve(n);
    vector<int> price(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> ve[i] >> price[i];
    }
    int res = LLONG_MAX;
    for (int i = 0; i < n; i++) {
        int val = max(0ll, price[i] - fun(s, ve[i]));
        if (val < res) {
            res = val;
        }
    }
    cout << res << endl;
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

We treat any contiguous block of slots [l,r] (1 ≤ l ≤ r ≤ M) as a “segment.” We need, for each length k, the number of segments of length k that, for every collaboration request (Ai,Bi), include at least one of Ai or Bi.

1. Monotonicity.
   If segment [i,j] is valid, then any expansion [k,ℓ] with k ≤ i < j ≤ ℓ remains valid.

2. Sliding‑window to find minimal R for each L.

• Build inv[pos] = list of request indices touching slot pos.
• Maintain two pointers L, R; an array cnt[1..N]; and cnt_zero = number of requests with cnt[i] == 0.
• Increase R until cnt_zero == 0. Then [L,R] is the minimal valid window.
• All lengths (R–L+1) through (M–L+1) get one valid segment via difference‑array updates.
• Remove slot L, increment L, update counts, and repeat.

1. Difference‑array and prefix sums.
   For each L with minimal R: ans[R-L+1] += 1; ans[M-L+2] -= 1;

Then prefix‑sum ans to obtain each f(k).

Complexity: O(N+M).

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

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

int N, M;
cin >> N >> M;

// inv[pos] = list of request‑indices (0…N‑1) that mention slot pos
vector<vector<int>> inv(M+2);

vector<int> A(N), B(N);
for(int i = 0; i < N; i++){
    cin >> A[i] >> B[i];
    inv[A[i]].push_back(i);
    inv[B[i]].push_back(i);
}

// cnt[i] = how many of the two endpoints of request i are currently in the window
vector<int> cnt(N, 0);
int cnt_zero = N;        // how many requests are currently uncovered (cnt[i]==0)

// difference‑array over lengths 1…M
vector<ll> diff(M+3, 0);

int R = 1;
// slide left end L from 1…M
for(int L = 1; L <= M; L++){
    // expand R until every request is covered (cnt_zero==0) or R>M
    while(R <= M && cnt_zero > 0){
        for(int idx : inv[R]){
            if(cnt[idx] == 0) 
                cnt_zero--;
            cnt[idx]++;
        }
        R++;
    }
    // if even the full [L…M] doesn’t cover all, we’re done
    if(cnt_zero > 0) break;

    // minimal valid window is [L…R-1], length = (R-1)-L+1 = R-L
    int minLen = R - L;
    // any extension up to length (M-L+1) also works
    int maxLen = M - L + 1;

    diff[minLen] += 1;
    diff[maxLen + 1] -= 1;

    // now remove slot L from window before incrementing L
    for(int idx : inv[L]){
        cnt[idx]--;
        if(cnt[idx] == 0) 
            cnt_zero++;
    }
}

// prefix‑sum the difference array to get answers for each k
vector<ll> ans(M+1, 0);
ll running = 0;
for(int k = 1; k <= M; k++){
    running += diff[k];
    ans[k] = running;
}

// output
for(int k = 1; k <= M; k++){
    cout << ans[k] << (k==M? '\n' : ' ');
}
return 0;

}

The problem states at each query, the odd number people will love some/none people of the 5 people ahead of them, similarly the even positioned people will love some/none people of the 5 people ahead of them. Starting from 1 to n, if the i-th person got x number of candies, he will give (x+1) candies to each who he loves. After its done for all i, find the total number of candies on the n-th person.

The solution is based on linear recurrence using Matrix Exponentiation.

Let, $$$f(x)$$$ = Total candies on the $$$x^{th}$$$ person after the distribution is done.

Here each term depends linearly on the previous five values plus a constant, all the coefficients are either 1 or 0. It can be shown that the $$$f$$$ can we written like this at any moment.

We capture this via an augmented state vector

For odd (x),

and for even (x),

where $$$(M_{2})$$$ is defined identically using $$$((a_{2},b_{2},c_{2},d_{2},e_{2}))$$$.

Since odd/even steps alternate, two consecutive transitions multiply by $$$(M_{1}M_{2})$$$. Write

Let

Then the state at (n) is

Compute $$$(P^{k})$$$ by binary exponentiation in $$$(O(\log n))$$$ time; if $$$(r=1)$$$, post‑multiply by $$$(M_1)$$$ if required.

Finally, build the base vector

and take the first component of $$$(\mathbf{v}(n))$$$ modulo the given modulus as the answer.

Time Complexity:

Each $$$(6\times6)$$$ multiplication is constant time, and exponentiation takes $$$(O(\log n))$$$ multiplications, giving overall $$$(O(\log n))$$$ per query case and hence $$$(q*O(\log n))$$$ for each test case, if considering constant we get $$$(216*q*O(\log n))$$$, 216 for matrix multiplication.

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

#define pb emplace_back
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define vb vector<bool>
#define vvll vector<vll>
#define vvi vector<vi>
#define ull unsigned long long
#define ui unsigned int
#define vp(a, b) vector<pair<a, b>>
#define endl "\n"
#define mems(a, x) memset((a), (x), sizeof(a))
#define fo(n, i, start) for (ll i = start; i <= n; i++)
#define rf(n, i, start) for (ll i = n; i >= start; i--)
#define f(n) for (ll i = 0; i < n; i++)
#define fr(n, m) f(n) fo(m - 1, j, 0)
#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define ff first
#define ss second
#define log2(n) 63 - __builtin_clzll(n)
#define pr(a)              \
    for (auto it : a)      \
        cout << it << " "; \
    cout << endl;
#define perr(a)            \
    for (auto it : a)      \
        cerr << it << " "; \
    cerr << endl;
const ll MOD = 1e9 + 7;

/*
========================================
Author:         Karan Agarwal
Institution:    IIITL
========================================
*/
vvll matrixmul(vvll &a, vvll &b)
{
    ll n = a.size(), m = b[0].size(), x = b.size();
    vvll res(n, vll(m, 0));
    fr(n, m)
    {
        fo(x - 1, k, 0)
        {
            res[i][j] += (a[i][k] * b[k][j]) % MOD, res[i][j] %= MOD;
        }
    }

    return res;
}

vvll matExpo(vvll mtx, ll p)
{
    ll sz = mtx.size();
    vvll res(sz, vll(sz, 0));
    f(sz) res[i][i] = 1;
    while (p)
    {
        if (p & 1)
            res = matrixmul(res, mtx);
        p >>= 1;
        mtx = matrixmul(mtx, mtx);
    }
    return res;
}
void solve()
{
    ll n, q;
    cin >> n >> q;
    cout << n - 1 << ' ';
    vvll mte(6, vll(6, 0));
    vvll mto(6, vll(6, 0));
    fo(4, i, 1) mte[i][i - 1] = 1;
    mte[5][5] = 1;
    fo(4, i, 1) mto[i][i - 1] = 1;
    mto[5][5] = 1;
    vll d(5), e(5);
    d[0] = 1, e[0] = 1;
    ll l = 1, r = 1;
    while (q--)
    {
        ll tp, x;
        cin >> tp >> x;
        f(6) mte[0][i] = 0, mto[0][i] = 0;
        if (tp == 1)
        {
            f(5) d[i] = 0;
            f(x) cin >> d[i];
        }
        if (tp == 2)
        {
            f(5) e[i] = 0;
            f(x) cin >> e[i];
        }
        l = 0, r = 0;
        f(5)
        {
            if (d[i] != 0)
            {
                if (d[i] & 1)
                    mte[0][d[i] - 1]++, l++;
                else
                    mto[0][d[i] - 1]++, r++;
            }
            if (e[i] != 0)
            {
                if (e[i] & 1)
                    mto[0][e[i] - 1]++, r++;
                else
                    mte[0][e[i] - 1]++, l++;
            }
        }
        mte[0][5] = l;
        mto[0][5] = r;
        vvll mtx = matrixmul(mto, mte);
        vvll base(6, vll(1, 0));
        base[5][0] = 1;
        rf(4, i, 0)
        {
            if (i & 1)
                fo(4, j, 0)
                { 
                    if (mte[0][j] && i + j + 1 <= 4)
                        base[i][0] += base[i + j + 1][0] + 1;
                }
            else
                fo(4, j, 0)
                {
                    if (mto[0][j] && i + j + 1 <= 4)
                        base[i][0] += base[i + j + 1][0] + 1;
                }
        }
        if (n <= 5)
        {
            cout << base[5 - n][0] << ' ';
            continue;
        }
        ll nn = n - 5;
        vvll expo = matExpo(mtx, nn / 2);
        base = matrixmul(expo, base);
        if (nn & 1)
            base = matrixmul(mte, base);
        cout << base[0][0] << ' ';
    }
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll tt = 1;
    cin >> tt;
    while (tt--)
    {
        solve();
    }
    return 0;
}

We model the situation as an undirected graph, where each node represents a grid cell along with its current momentum — that is, the direction you're moving in and how many steps you've taken in that direction so far.

From any node, you can move one step in any of the 6 directions (±x, ±y, ±z). If the direction is the same as before, the cost decreases based on your momentum — fewer steps cost less: $$$5 \rightarrow 4 \rightarrow 2 \rightarrow 1$$$.
If the direction changes, the cost resets to $$$5$$$ and momentum resets as well.

Landing on any planet node adds extra time:

• Intermediate planets: $$$+20$$$ minutes (landing + takeoff)
• Final planet: $$$+10$$$ minutes

In both cases, momentum is reset. The procedure always starts with takeoff and ends with landing.

Total number of states is approximately

Each state has at most 6 outgoing edges.
We run Dijkstra’s algorithm over this expanded graph.

Time complexity:

This fits comfortably within standard time and memory limits.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
struct State {
    int cost, x, y, z, lastdir, speedlevel;
    bool operator>(const State &other) const {
        return cost > other.cost;
    }
};
 
int val = 0;
 
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> planets(n);
 
    for(int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x++; y++; z++;
        planets[i] = {x, y, z};
 
    }
 
 
 
 
    vector<vector<vector<int>>> space(54, vector<vector<int>>(54, vector<int>(54, 0)));
    for(int i = 0; i < n; i++) {
        space[planets[i][0]][planets[i][1]][planets[i][2]] = i+1;
    }
 
    int _x = 53, _y = 53, _z = 53;
 
    // {x, y, z, lastdir, speedlevel}
    vector<vector<vector<vector<vector<int>>>>> dist(_x+1, 
        vector<vector<vector<vector<int>>>>(_y+1, 
            vector<vector<vector<int>>>(_z+1, 
                vector<vector<int>>(7, vector<int>(4, 1e18)))));
 
    const int dx[] = {1, -1, 0, 0, 0, 0};
    const int dy[] = {0, 0, 1, -1, 0, 0};
    const int dz[] = {0, 0, 0, 0, 1, -1};
    const int speed_cost[] = {5, 4, 2, 1};
 
    priority_queue<State, vector<State>, greater<State>> st;
    st.push({10, planets[0][0], planets[0][1], planets[0][2], -1, 0});
 
    while(!st.empty()) {
        auto v = st.top();
        st.pop();
        int dd = v.cost, x = v.x, y = v.y, z = v.z, lastdir = v.lastdir, speedlevel = v.speedlevel;
 
        // if(lastdir != -1 && dd > dist[x][y][z][lastdir][speedlevel]) continue;
 
 
        for(int dir = 0; dir < 6; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            int nz = z + dz[dir];
            if(nx < 0 || nx > _x || ny < 0 || ny > _y || nz < 0 || nz > _z) continue;
 
            int new_speedlevel = (dir == lastdir) ? min(speedlevel + 1LL, 3LL) : 0;
            int move_cost = speed_cost[new_speedlevel];
            int total_cost = dd + move_cost;
 
            if(space[nx][ny][nz] != 0) {
                if(space[nx][ny][nz] == n) {
                    dist[nx][ny][nz][6][0] = min(dist[nx][ny][nz][6][0], total_cost + 10);
                } else {
                    if(total_cost + 20 < dist[nx][ny][nz][6][0]) {
                        dist[nx][ny][nz][6][0] = total_cost + 20;
                        st.push({total_cost + 20, nx, ny, nz, 6, 0});
                    }
                }
            } else {
                if(total_cost < dist[nx][ny][nz][dir][new_speedlevel]) {
                    dist[nx][ny][nz][dir][new_speedlevel] = total_cost;
                    st.push({total_cost, nx, ny, nz, dir, new_speedlevel});
                }
            }
        }
    }
 
    int ans = 1e18;
    int ex = planets[n-1][0], ey = planets[n-1][1], ez = planets[n-1][2];
    for(int i = 0; i < 7; i++) {
        for(int j = 0; j < 4; j++) {
            ans = min(ans, dist[ex][ey][ez][i][j]);
        }
    }
    cout << ans << '\n';
}
 
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
 
 
    while(t--) solve();
 
 
    return 0;
}

We are given a matrix of happiness values where the element at a_i,j represents the happiness of student j traveling in bus i. The task is to assign exactly one bus to each student while using at most n−1 buses, and our goal is to maximize the minimum happiness among all students.

First, for each student, we compute the maximum happiness they can get across all buses. This is stored in an array maxi[j], which holds the best possible happiness value for student j. If the number of students n is greater than the number of buses m, then we must use all the buses, and the result is simply the minimum value among the maxi array, i.e., the student with the least possible best happiness.

When n ≤ m, the goal is to pick at most n−1 buses in such a way that every student gets their maximum happiness from one of those buses. If it's possible to satisfy all students this way, we compute the minimum of their best values (maxi) directly.

However, if it’s not possible — we can say that no two students can get their maximum happiness from the same bus. Then we can do this: Suppose we decide to include a specific bus in our final selection. Since we can only use n−1 buses at max, that leaves us with n−2 additional buses to freely choose. So for this scenario, we assign the top 2 students (i.e., the 2 students who get the most happiness from the selected bus) to this fixed bus, and assign the remaining n−2 students to other buses which give them their maximum happiness.

Thus, for each bus, we simulate this configuration: take the two students who benefit most from it and ensure the rest get their maximum happiness from other buses. We then calculate the minimum happiness over all students in this arrangement. The answer is the maximum of these minimums across all bus choices.

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
void solve(){
    int m,n;
    cin >> n >> m;
    vector<vector<int>> ve(n, vector<int>(m, 0));
    vector<int> maxi(n, 0);
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin >> ve[j][i];
            maxi[j] = max(maxi[j], ve[j][i]);
        }
    }
 
    int val = LLONG_MAX;
    if(n > m){
        for(auto it : maxi) val = min(val, it);
        cout << val << endl;
        return;
    }
 
    val = 0;
    vector<vector<int>> maxi1(m, maxi);
    for(int i = 0; i < m; i++){
        vector<pair<int, int>> temp(n);
        for(int j = 0; j < n; j++){
            temp[j] = {ve[j][i], j};
        }
        sort(temp.rbegin(), temp.rend());
        maxi1[i][temp[0].second] = temp[0].first;
        maxi1[i][temp[1].second] = temp[1].first;
        int tval = *min_element(maxi1[i].begin(), maxi1[i].end());
        val = max(val, tval);
    }
    cout << val << endl;
}
 
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}