Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- class Node {
- public:
- Node* pnext, *pprev;
- int data;
- Node(int x = 0): data(x), pnext(nullptr), pprev(nullptr) {}
- Node(int x, Node* next, Node* prev = nullptr): data(x), pnext(next), pprev(prev) {}
- };
- class Deque {
- private:
- Node* head;
- Node* tail;
- public:
- Deque(): head(new Node()), tail(new Node()) {
- head->pnext = tail;
- tail->pprev = head;
- }
- int pop_front() {
- if (head->pnext == tail)
- throw out_of_range("Deque is empty!");
- int res = head->pnext->data;
- auto oldNode = head->pnext;
- head->pnext = oldNode->pnext;
- head->pnext->pprev = head;
- delete oldNode;
- return res;
- }
- void push_back(int elem) {
- auto newNode = new Node(elem, tail, tail->pprev);
- tail->pprev->pnext = newNode;
- tail->pprev = newNode;
- }
- int pop_back() {
- if (head->pnext == tail)
- throw out_of_range("Deque is empty!");
- auto oldNode = tail->pprev;
- int res = oldNode->data;
- tail->pprev = oldNode->pprev;
- tail->pprev->pnext = tail;
- delete oldNode;
- return res;
- }
- bool empty() {
- return head->pnext == tail;
- }
- int back() {
- if (this->empty())
- throw out_of_range("Stack is empty");
- return tail->pprev->data;
- }
- int front() {
- if (this->empty())
- throw out_of_range("Stack is empty");
- return head->pnext->data;
- }
- ~Deque() {
- auto e = head;
- auto d = head;
- while (d != tail) {
- d = e;
- e = e->pnext;
- delete d;
- }
- }
- };
- class QueueWithMin {
- Deque deque;
- public:
- QueueWithMin(): deque() {}
- void push(int elem) {
- while (!deque.empty() && deque.back() > elem) {
- deque.pop_back();
- }
- deque.push_back(elem);
- }
- void pop(int removed_elem) {
- if (deque.front() == removed_elem)
- deque.pop_front();
- }
- int min() {
- return deque.front();
- }
- };
- int main() {
- int n, L;
- cin >> n >> L;
- vector<vector<int>> data(n, vector<int>(n));
- for (auto&& row : data) {
- for (int i = 0; i < n; i++) {
- cin >> row[i];
- }
- }
- vector<vector<int>> mins(n, vector<int>(n));
- // mins[i][j] = min(data[i][j - L + 1 : j + 1]), i >= L-1, j >= L-1
- // mins[i][j] = 0, otherwise
- for (int i = 0; i < n; i++) {
- QueueWithMin q;
- for (int k = 0; k < L; k++)
- q.push(data[i][k]);
- for (int j = 0; j < n - L + 1; j++) {
- mins[i][j+L-1] = q.min();
- q.pop(data[i][j]);
- if (j + L < n) {
- q.push(data[i][j + L]);
- }
- }
- }
- vector<vector<int>> ans(n, vector<int>(n));
- // ans[i][j] = min(mins[i - L + 1 : i + 1][j]), i >= L-1, j >= L-1
- // ans[i][j] = 0
- for (int j = 0; j < n; j++) {
- QueueWithMin q;
- for (int k = 0; k < L-1 && j >= L-1; k++)
- q.push(data[k][j]);
- q.push(mins[L-1][j]);
- for (int i = 0; i < n - L + 1; i++) {
- ans[i+L-1][j] = q.min();
- q.pop(mins[i][j]);
- if (i + L < n) {
- q.push(mins[i + L][j]);
- }
- }
- }
- for (int i = L-1; i < n; i++) {
- for (int j = L-1; j < n; j++) {
- cout << ans[i][j] << " ";
- }
- cout << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement