verify/codeforces/codeforces-1195E.test.cpp

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Problem: https://codeforces.com/problemset/problem/1195/E

Depends on

• library/contest/template-minimal.hpp
• library/dynamic-programming/max-deque.hpp
• library/dynamic-programming/min-deque.hpp

Code

#define PROBLEM "https://codeforces.com/problemset/problem/1195/E"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/dynamic-programming/min-deque.hpp"
#include "../../library/dynamic-programming/max-deque.hpp"

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, a, b;
	cin >> n >> m >> a >> b;
	long long g, x, y, z;
	cin >> g >> x >> y >> z;
	vector<vector<int>> grid(n + 1, vector<int>(m + 1));
	vector<vector<int>> row_min(n + 1, vector<int>(m + 1));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			grid[i][j] = g;
			g = (g * x + y) % z;
		}
	}
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		MinDeque<int> d;
		for (int j = 0; j < b; ++j) {
			d.push_back(grid[i][j]);
		}
		for (int j = 0; j <= m - b; ++j) {
			row_min[i][j] = d.get();
			d.pop_front();
			d.push_back(grid[i][j + b]);
		}
	}
	for (int j = 0; j <= m - b; ++j) {
		MinDeque<int> d;
		for (int i = 0; i < a; ++i) {
			d.push_back(row_min[i][j]);
		}
		for (int i = 0; i <= n - a; ++i) {
			ans += d.get();
			d.pop_front();
			d.push_back(row_min[i + a][j]);
		}
	}
	cout << ans << '\n';
	return 0;
}

#define PROBLEM "https://codeforces.com/problemset/problem/1195/E"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

template <class T> struct MinDeque {
	int lo = 0, hi = -1;

	std::deque<std::pair<T, int>> d;
	void push_back(T x) { // add to back

		while ((int)d.size() && d.back().first >= x) d.pop_back();
		d.push_back({x, ++hi});
	}

	void pop_front() { // delete from front

		if (d.front().second == lo++) d.pop_front();
	}

	T get() {
		return (int)d.size() ? d.front().first : std::numeric_limits<T>::max();
	}
};

template <class T> struct MaxDeque {
	std::deque<std::pair<T, int>> mx;
	std::deque<int> tmp;

	int l = 0,r = -1;

	int pop_front() {
		if (mx.front().second == l++) mx.pop_front();
		int t = tmp.front();
		tmp.pop_front();
		return t;
	}

	T get() {
		if ((int)mx.size() == 0) return std::numeric_limits<T>::min();
		return mx.front().first;
	}

	void push_back(T x) {
		while ((int)mx.size() && mx.back().first <= x) mx.pop_back();
		mx.push_back({x, ++r});
		tmp.push_back(x);
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, a, b;
	cin >> n >> m >> a >> b;
	long long g, x, y, z;
	cin >> g >> x >> y >> z;
	vector<vector<int>> grid(n + 1, vector<int>(m + 1));
	vector<vector<int>> row_min(n + 1, vector<int>(m + 1));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			grid[i][j] = g;
			g = (g * x + y) % z;
		}
	}
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		MinDeque<int> d;
		for (int j = 0; j < b; ++j) {
			d.push_back(grid[i][j]);
		}
		for (int j = 0; j <= m - b; ++j) {
			row_min[i][j] = d.get();
			d.pop_front();
			d.push_back(grid[i][j + b]);
		}
	}
	for (int j = 0; j <= m - b; ++j) {
		MinDeque<int> d;
		for (int i = 0; i < a; ++i) {
			d.push_back(row_min[i][j]);
		}
		for (int i = 0; i <= n - a; ++i) {
			ans += d.get();
			d.pop_front();
			d.push_back(row_min[i + a][j]);
		}
	}
	cout << ans << '\n';
	return 0;
}

Back to top page