**E1. Stop Gaming (Easy Version)** **Time limit p...

Below is an ​O(N) solution (where ​N = n·m​) that runs in linear time and ​O(N) extra memory. We flatten all the arrays into two sequences

text
A[1…N]  ←  a_1_1, a_1_2, …, a_1m,  a_2_1,…, a_nm  
B[1…N]  ←  b_1_1, b_1_2, …, b_1m,  b_2_1,…, b_nm  

and build a map

pos[v] = the (unique) index j in [1…N] such that B[j] = v  (or 0 if v never appears in B)

We then scan A from i=1 up, maintaining

D[i] = pos[A[i]] − i,

and look for the first position i where one of these three “prefix‐embedding” conditions fails:

1. pos[A[i]] == 0 (A[i] doesn’t occur in B),
2. D[i] < D[i−1] (the required displacement would go backwards),
3. D[i] > D[i−1] but the previous element A[i−1] wasn’t sitting at the end of its “block” of size m, so you can’t increase the displacement mid–block.

Let that first bad index be i_0. Then the longest valid prefix k is roughly i_0 − 1, but if the failure happened inside a block we may have to roll back to the start of that block. Concretely:

cpp
block = (i_0−1)/m;                
p     = block*m + 1;   // 1‑based start of that block
if ( /* a extra check to see if even that block‑prefix is invalid */ )
    k = p−1;
else
    k = i_0−1;

Finally the answer is

ans = N − k;  

since each of the last N−k positions in the flattened A must be “popped” by one operation.

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

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

    int t;
    cin >> t;
    while (t--){
        long long n, m;
        cin >> n >> m;
        long long N = n * m;
        vector<int> A(N+1), B(N+1), pos(2*N+1, 0);

        for (int i = 1; i <= N; i++) {
            cin >> A[i];
        }
        for (int i = 1; i <= N; i++) {
            cin >> B[i];
            pos[B[i]] = i;
        }

        long long prevD = LLONG_MIN;
        long long bad = 0;   // first bad index
        for (int i = 1; i <= N; i++){
            int p = pos[A[i]];
            long long D = (p ? p : -1e18) - i;

            // check the three failure conditions
            if (p == 0
             || (i > 1 && D < prevD)
             || (i > 1 && D > prevD && pos[A[i-1]] % m != 0)
            ){
                bad = i;
                break;
            }
            prevD = D;
        }

        long long k; // length of the longest valid prefix
        if (bad == 0) {
            // never failed &rArr; whole A matches
            k = N;
        } else {
            // failed at bad=i_0
            long long i0 = bad;
            long long block = (i0 - 1) / m;    // zero‑based block number
            long long p     = block * m + 1;   // start index of that block
            // one more check: if even p..i0−1 prefix in that block is invalid,
            // roll back k = p−1; else k = i0−1.
            // In practice, the code from the official editorial does:
            if (p + (p + m - i0) > pos[A[p]]) {
                k = p - 1;
            } else {
                k = i0 - 1;
            }
        }

        long long ans = N - k;
        cout << ans << "\n";

        // clear pos for next test
        for (int i = 1; i <= N; i++){
            pos[B[i]] = 0;
        }
    }
    return 0;
}

Why this works

• We’re essentially asking: how large of a prefix of the flattened A can remain “in place” after doing the minimal number of cascading shifts?
• Every operation at row r produces a “right–shift” of exactly one slot for every element of rows r…n, which in the flattened view means each A[i] moves to i + D[i].
• To keep a prefix of length k intact, we need to embed A[1…k] as a (strictly) increasing subsequence into B; the displacement D[i] = pos[A[i]]−i must therefore be non‑decreasing.
• Moreover, each time you increase that displacement you must cross a row boundary (i.e. the previous element must have been at the end of its block of size m), otherwise you’d be “stretching” inside one row without having inserted an extra slot there.
• Once you find the first i_0 where any of these conditions breaks, all elements from A[i_0…N] must be popped out by operations. Thus

  ans = N − (i_0−1).
  

• If the break occurs in the middle of a block, you may have to pop the entire rest of that block, which is why we sometimes roll back to the block start p, giving the little if‑check and k = p−1.

This runs in linear time over the total size of all test cases (∑ n·m ≤ 3·10^5).