Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- #define fast cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
- #define F first
- #define S second
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define PI 3.14159265
- #define int long long
- using namespace std;
- const int INF = 1e9 + 9;
- const int mod = 1e9 + 7;
- const int MAXN = 2 * 1e5;
- const double EPS = 0.0000000001;
- signed main() {
- fast;
- int n, m, a, b;
- cin >> n >> m;
- int t[n][m];
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- cin >> t[i][j];
- }
- }
- cin >> a >> b;
- int d[n][m - b + 1];
- for(int i = 0; i < n; i++) {
- deque<int> deq;
- for(int j = 0; j < b; j++) {
- while(!deq.empty() && deq.back() > t[i][j]) deq.pop_back();
- deq.push_back(t[i][j]);
- }
- d[i][0] = deq.front();
- for(int j = b; j < m; j++) {
- if (t[i][j - b] == deq.front()) deq.pop_front();
- while(!deq.empty() && deq.back() > t[i][j]) deq.pop_back();
- deq.push_back(t[i][j]);
- d[i][j - b + 1] = deq.front();
- }
- }
- int r[n - a + 1][m - b + 1];
- for(int j = 0; j < m - b + 1 ; j++) {
- deque<int> deq;
- for(int i = 0; i < a; i++) {
- while(!deq.empty() && deq.back() > d[i][j]) deq.pop_back();
- deq.push_back(d[i][j]);
- r[0][j] = deq.front();
- }
- for(int i = a; i < n; i++) {
- if (d[i - a][j] == deq.front()) deq.pop_front();
- while(!deq.empty() && deq.back() > d[i][j]) deq.pop_back();
- deq.push_back(d[i][j]);
- r[i - a + 1][j] = deq.front();
- }
- }
- for(int i = 0; i < n - a + 1; i++) {
- for(int j = 0; j < m - b + 1; j++) cout << r[i][j] << " ";
- cout << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement