1777C - Quiz Master - CodeForces Solution

#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <time.h>
#include <vector>

#define INF 1E9
#define INF64 2E18

using namespace std;

template<class T1, class T2> void pr(const pair<T1,T2>& x);
template<class T, size_t SZ> void pr(const array<T,SZ>& x);
template<class T> void pr(const vector<T>& x);
template<class T, class C> void pr(const set<T,C>& x);
template<class T, class C> void pr(const multiset<T,C>& x);
template<class T1, class T2> void pr(const map<T1,T2>& x);
template<class... T> void pr(const tuple<T...>& tup);

template<class T> void pr(const T& x) { cout << x; }
template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
  pr(first); pr(rest...);
}
template<class T1, class T2> void pr(const pair<T1,T2>& x) {
  pr("{",x.first,", ",x.second,"}");
}
template<class T> void prContain(const T& x) {
  pr("{");bool fst = 1; for(auto &a: x) pr(!fst?", ":"",a), fst = 0;pr("}");
}
template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
template<class T> void pr(const vector<T>& x) { prContain(x); }
template<class T, class C> void pr(const set<T,C>& x) { prContain(x); }
template<class T, class C> void pr(const multiset<T,C>& x) { prContain(x); }
template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }

template<class T, size_t... I>
void pr(const T& tup, index_sequence<I...>) {
  pr("("); (..., (cout << (I == 0? "" : ", ") << get<I>(tup))); pr(")");
}
template<class... T>
void pr (const tuple<T...>& tup) {
  pr(tup, make_index_sequence<sizeof...(T)>());
}
void ps() { pr("\n"); }
void _ps_continue() { pr("\n"); }
template<class Arg, class... Args> void _ps_continue(const Arg& first, const Args&... rest) {
  pr(" ", first); _ps_continue(rest...);
}
template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) {
  pr(first); _ps_continue(rest...);
}

template<typename T> int remin(T& a,const T& b){if(b<a){a=b;return true;}return false;}
template<typename T> int remax(T& a,const T& b){if(a<b){a=b;return true;}return false;}

typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int NN = 320;
vi primes;
void get_primes(int nn = NN) {
  vector<bool> scieve(nn, true);
  primes.push_back(2);
  for (int i = 3; i*i < nn; i+=2) {
    if (scieve[i]) {
      for (int j = i*i; j < nn; j+=2*i){
        scieve[j] = false;
      }
    }
  }
  for (int i = 3; i < nn; i += 2) {
    if (scieve[i]) primes.push_back(i);
  }
  return;
}

vi p[100005];


template<class T = ll>
struct Fenwick_Tree {
  vector<T> bit;
  int _n;
  ll total = 0;
  Fenwick_Tree(int n): _n(n) {
    bit.resize(n+1);
  }
  inline int low_bit(int idx) { return idx&(-idx); }
  T sum(int idx) {
    T ret = 0;
    int k = idx + 1;
    while (k > 0) {
      ret += bit[k];
      k -= low_bit(k);
    }
    return ret;
  }
  void update(int idx, int v) {
    total += v;
    assert(0 <= idx && idx < _n);
    int k = idx + 1;
    while (k < _n+1) {
      bit[k] += v;
      k += low_bit(k);
    }
  }
  T query(int l, int r) {
    assert(r < _n);
    assert(l <= r);
    return sum(r) - sum(l-1);
  }
  T query_lte(int x) {
    if (x < 0) return 0;
    return query(0, x);
  }
  T query_gte(int x) {
    return total - query_lte(x-1);
  }
};


vi divs(int x, int m) {
  vi d;
  for (int i = 1; i*i <= x; ++i) {
    if (x%i == 0) {
      if (i <= m) d.push_back(i);
      if (x/i <= m) d.push_back(x/i);
      if (i == x/i && i <= m) d.pop_back();
    }
  }
  return d;
}

void solve() {
  int n, m; scanf("%d%d", &n, &m);
  vi a(n);
  int mx = m;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    remax(mx, a[i]);
  }
  sort(a.begin(), a.end());
  a.resize(distance(a.begin(), unique(a.begin(), a.end())));
  n = a.size();
  for (int i = 0; i < n; ++i) {
    p[i] = divs(a[i], m);
    // ps(a[i], p[i]);
  }
  multiset<int> mst;

  int ans = INF;
  vi cnt(mx+1);
  Fenwick_Tree<ll> ft(mx+1);

  // from l to r excluded
  for (int l = 0, r = 0; l < n && r <= n; ) {
    // ps(l, r, mst, ft.query(1, m));
    if (ft.query(1, m) < m) {
      if (r == n) break;
      for (int el: p[r]) {
        mst.insert(el);
        cnt[el]++;
        if (cnt[el] == 1) {
          ft.update(el, +1);
        }
      }
      ++r;
    } else {
      remin(ans, a[r-1] - a[l]);
      for (int el: p[l]) {
        mst.erase(mst.find(el));
        cnt[el]--;
        if (cnt[el] == 0) {
          ft.update(el, -1);
        }
      }
      ++l;
    }
  }
  ps(ans == INF ? -1: ans);
}

int main(int argc, const char **argv) {
  // get_primes();
  // ps(primes.size());
  // ps(primes.back());
  int TT; scanf("%d", &TT);
  for (int tt = 1; tt <= TT; ++tt) {
    solve();
  }
  return 0;
}