fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. // Data structure to store value and its original sequence index
  8. struct Element {
  9.     int val;
  10.     int id;
  11.  
  12.     // Comparison function to sort in ascending order of value
  13.     bool operator<(const Element& other) const {
  14.         return val < other.val;
  15.     }
  16. };
  17.  
  18. int main() {
  19.     // Optimize I/O in C++
  20.     ios_base::sync_with_stdio(false);
  21.     cin.tie(NULL);
  22.  
  23.     int n, m;
  24.     if (!(cin >> n >> m)) return 0;
  25.  
  26.     vector<Element> a;
  27.     a.reserve(n * m);
  28.  
  29.     // Read input data
  30.     for (int i = 1; i <= n; ++i) {
  31.         for (int j = 1; j <= m; ++j) {
  32.             int v;
  33.             cin >> v;
  34.             a.push_back({v, i});
  35.         }
  36.     }
  37.  
  38.     // Step 1: Sort all elements in ascending order by value
  39.     sort(a.begin(), a.end());
  40.  
  41.     // Step 2: Two Pointers Technique (Sliding Window)
  42.     vector<int> freq(n + 1, 0);
  43.     int unique_count = 0;
  44.     int ans = 2e9 + 7; // Initialize answer with a very large value
  45.     int total_elements = n * m;
  46.  
  47.     int L = 0;
  48.     for (int R = 0; R < total_elements; ++R) {
  49.         // Expand the window to the right (Pointer R)
  50.         if (freq[a[R].id] == 0) {
  51.             unique_count++;
  52.         }
  53.         freq[a[R].id]++;
  54.  
  55.         // Shrink the window from the left (Pointer L) when all N sequences are present
  56.         while (unique_count == n) {
  57.             ans = min(ans, a[R].val - a[L].val);
  58.  
  59.             freq[a[L].id]--;
  60.             if (freq[a[L].id] == 0) {
  61.                 unique_count--;
  62.             }
  63.             L++; // Move left pointer
  64.         }
  65.     }
  66.  
  67.     // Step 3: Print result
  68.     cout << ans << "\n";
  69.  
  70.     return 0;
  71. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GDGNMw
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!