SHARE
TWEET

Untitled

a guest Jul 22nd, 2019 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  3. #define fast cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  4. #define F first
  5. #define S second
  6. #define all(x) (x).begin(), (x).end()
  7. #define rall(x) (x).rbegin(), (x).rend()
  8. #define PI 3.14159265
  9. #define int long long
  10. using namespace std;
  11.  
  12. const int INF = 1e9 + 9;
  13. const int mod = 1e9 + 7;
  14. const int MAXN = 2 * 1e5;
  15. const double EPS = 0.0000000001;
  16.  
  17.  
  18. signed main() {
  19.     fast;
  20.     int n, m, a, b;
  21.     cin >> n >> m;
  22.  
  23.     int t[n][m];
  24.     for(int i = 0; i < n; i++) {
  25.         for(int j = 0; j < m; j++) {
  26.             cin >> t[i][j];
  27.         }
  28.     }
  29.  
  30.     cin >> a >> b;
  31.  
  32.     int d[n][m - b + 1];
  33.  
  34.     for(int i = 0; i < n; i++) {
  35.         deque<int> deq;
  36.  
  37.         for(int j = 0; j < b; j++) {
  38.             while(!deq.empty() && deq.back() > t[i][j]) deq.pop_back();
  39.             deq.push_back(t[i][j]);
  40.  
  41.         }
  42.  
  43.         d[i][0] = deq.front();
  44.  
  45.  
  46.         for(int j = b; j < m; j++) {
  47.             if (t[i][j - b] == deq.front()) deq.pop_front();
  48.  
  49.             while(!deq.empty() && deq.back() > t[i][j]) deq.pop_back();
  50.             deq.push_back(t[i][j]);
  51.  
  52.             d[i][j - b + 1] = deq.front();
  53.         }
  54.  
  55.  
  56.     }
  57.  
  58.  
  59.     int r[n - a + 1][m - b + 1];
  60.  
  61.     for(int j = 0; j < m - b + 1 ; j++) {
  62.         deque<int> deq;
  63.  
  64.  
  65.         for(int i = 0; i < a; i++) {
  66.             while(!deq.empty() && deq.back() > d[i][j]) deq.pop_back();
  67.             deq.push_back(d[i][j]);
  68.  
  69.             r[0][j] = deq.front();
  70.         }
  71.  
  72.  
  73.         for(int i = a; i < n; i++) {
  74.             if (d[i - a][j] == deq.front()) deq.pop_front();
  75.             while(!deq.empty() && deq.back() > d[i][j]) deq.pop_back();
  76.             deq.push_back(d[i][j]);
  77.  
  78.             r[i - a + 1][j] = deq.front();
  79.         }
  80.  
  81.     }
  82.  
  83.     for(int i = 0; i < n - a + 1; i++) {
  84.         for(int j = 0; j < m - b + 1; j++) cout << r[i][j] << " ";
  85.         cout << endl;
  86.     }
  87.  
  88.     return 0;
  89. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top