fork download 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <climits>
  5. #include <cstring>
  6. #include <utility>
  7. #include <vector>
  8. #include <string>
  9. #include <cstdio>
  10. #include <bitset>
  11. #include <ctime>
  12. #include <cmath>
  13. #include <stack>
  14. #include <list>
  15. #include <set>
  16. #include <map>
  17.  
  18. using namespace std;
  19.  
  20. #define sci stack <int>
  21. #define vci vector <int>
  22. #define vcs vector <string>
  23. #define vcd vector <double>
  24. #define vci64 vector <long long>
  25. #define seti set <int>
  26. #define mseti multiset <int>
  27.  
  28. const int maxn = 1000 + 5;
  29. const int maxm = 1000 + 5;
  30.  
  31. typedef unsigned int uint;
  32. typedef long long int64;
  33. typedef unsigned long long uint64;
  34.  
  35. template <class T> inline T Sqr(const T & x) { return x * x; }
  36. template <class T> inline T Abs(const T & x) { return x > 0 ? x : -x; }
  37. template <class T> inline T Min(const T & a, const T & b) { return a < b ? a : b; }
  38. template <class T> inline T Max(const T & a, const T & b) { return a > b ? a : b; }
  39. template <class T> inline T Ksm(const T & a, const T & b, const T & m) { T _ = 1; for (; b; b >>= 1, a = a * a % m) (b & 1) ? _ = _ * a % m : 0; return _ % m; }
  40. template <class T> inline void Swap(T & a, T & b) { T _; _ = a; a = b; b = _; }
  41.  
  42. struct node { int data, wh; };
  43.  
  44. int a, b, n, h, ans = INT_MAX;
  45. int mat[maxn][maxn], mit[maxn][maxn];
  46.  
  47. int getint()
  48. {
  49.    char ch = getchar(); int result = 0, res = 1;
  50.    for (; '0' > ch || ch > '9'; ch = getchar()) ch == '-' ? res = -1 : 0;
  51.    for (; '0' <= ch && ch <= '9'; result = result * 10 + ch - '0', ch = getchar());
  52.    return result * res;
  53. }
  54.  
  55. int bit[20], p;
  56. void putint(int64 ans)//正数
  57. {
  58.    if (bit[0] = p = 0, ans == 0) ++p;
  59.    else for (; ans; bit[p++] = ans % 10, ans /= 10);
  60.    for (--p; p >= 0; --p) putchar('0' + bit[p]);
  61.    putchar('\n');
  62. }
  63.  
  64. bool cmp_(node a, node b) { return (a.data == b.data) ? a.wh < b.wh : a.data < b.data; }
  65. bool _cmp(node a, node b) { return (a.data == b.data) ? a.wh < b.wh : a.data > b.data; }
  66.  
  67. void prepare()
  68. {
  69.    node q[maxn], p[maxn];
  70.    int qhead = 1, qtail = n, phead = 1, ptail = n;
  71.    for (int i = 1; i <= n; ++i) q[i] = p[i] = (node) { getint(), i };
  72.    sort(q + 1, q + n + 1, cmp_), sort(p + 1, p + n + 1, _cmp);
  73.    mit[h][1] = q[1].data, mat[h][1] = p[1].data;
  74.    for (int i = 2; i <= b - n + 1; ++i)
  75.    {
  76.       int x = getint();
  77.       for (; q[qhead].wh < i; ++qhead);
  78.       for (; qhead <= qtail && q[qtail].data > x; --qtail);
  79.       q[++qtail] = (node) { x, i + n - 1 };
  80.       mit[h][i] = q[qhead].data;
  81.       for (; p[phead].wh < i; ++phead);
  82.       for (; phead <= ptail && p[ptail].data < x; --ptail);
  83.       p[++ptail] = (node) { x, i + n - 1 };
  84.       mat[h][i] = p[phead].data;
  85.    }
  86. }
  87.  
  88. void work()
  89. {
  90.    node q[maxn], p[maxn];
  91.    int qhead = 1, qtail = n, phead = 1, ptail = n;
  92.    for (int i = 1; i <= n; ++i) q[i] = (node) { mit[i][h], i };
  93.    for (int i = 1; i <= n; ++i) p[i] = (node) { mat[i][h], i };
  94.    sort(q + 1, q + n + 1, cmp_), sort(p + 1, p + n + 1, _cmp);
  95.    ans = Min(ans, p[1].data - q[1].data);
  96.    for (int i = 2; i <= a - n + 1; ++i)
  97.    {
  98.       int minx = mit[i + n - 1][h], maxx = mat[i + n - 1][h];
  99.       for (; q[qhead].wh < i; ++qhead);
  100.       for (; qhead <= qtail && q[qtail].data > minx; --qtail);
  101.       q[++qtail] = (node) { minx, i + n - 1 };
  102.       for (; p[phead].wh < i; ++phead);
  103.       for (; phead <= ptail && p[ptail].data < maxx; --ptail);
  104.       p[++ptail] = (node) { maxx, i + n - 1 };
  105.       ans = Min(ans, p[phead].data - q[qhead].data);
  106.    }
  107. }
  108.  
  109. int main()
  110. {
  111. #ifndef ONLINE_JUDGE
  112.    freopen("1047.in", "r", stdin);
  113.    freopen("1047.out", "w", stdout);
  114. #endif
  115.  
  116.    a = getint(), b = getint(), n = getint();
  117.    for (int i = 1; i <= a; ++i) h = i, prepare();
  118.    for (int i = 1; i <= b - n + 1; ++i) h = i, work();
  119.    putint(ans);
  120.  
  121.    return 0;
  122. }
Success #stdin #stdout 0s 10792KB
comments (?)
stdin 
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
stdout 
1
https://ideone.com/yfno6L
language:
C++ (gcc 8.3)
created:
12 years 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!