TLE on #2 #10

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int N = 1000010, M = 100;
const ll inf = 1e18;

int n, m, pos[M], idx;
map<ll, int> mp;
struct Node
{
    ll x, id;
    bool operator <(const Node &W) { return x < W.x; }
}c[N];

template <typename T> inline void read(T &x)
{
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

inline int get(ll x)
{
    if (mp.count(x)) return mp[x];
    return mp[x] = ++ idx;
}

int main()
{
    read(n), read(m);
    for (int i = 1; i <= m; i ++ )
    {
        int t;
        read(t);
        while (t -- )
        {
            ll x;
            read(x);
            c[ ++ idx] = {x, i};
        }
    }
    idx = 0;
    sort(c + 1, c + n + 1);
    int cnt = 0, l = 1; ll min_dist = inf;
    for (int i = 1; i <= n; i ++ )
    {
        if (pos[c[i].id] == 0) cnt ++ ;
        pos[c[i].id] = get(c[i].x);
        while (l < i && get(c[l].x) < pos[c[l].id]) l ++ ;
        if (cnt == m && c[i].x - c[l].x < min_dist) min_dist = c[i].x - c[l].x;
    }
    printf("%lld\n", min_dist);
    return 0;
}