Submission #2601442

---

Source Code Expand

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

long long H, W, N, M, D, S, A[100009], B1[100009], B2[100009]; vector<long long>G[100009];
multiset<long long>State;

void add(long long V) {
	/*auto pos = State.begin();
	while (pos != State.end()) { cout << *pos << " "; pos++; }cout << endl;
	cout << S << endl << endl;
	cout << "add " << V << endl;*/

	auto pos1 = State.lower_bound(V);
	auto pos2 = pos1; pos2--;
	long long L = *pos2, R = *pos1;
	if (R - L - 1 > D && L != V && R != V) {
		S++;
		if (R - V - 1 <= D) S += R - V - 1;
		if (V - L - 1 <= D) S += V - L - 1;
	}
	State.insert(V);
}
void lose(long long V) {
	/*auto pos = State.begin();
	while (pos != State.end()) { cout << *pos << " "; pos++; }cout << endl;
	cout << S << endl << endl;
	cout << "lose " << V << endl;*/
	auto pos0 = State.lower_bound(V); State.erase(pos0);
	auto pos1 = State.lower_bound(V);
	auto pos2 = pos1; pos2--;
	long long L = *pos2, R = *pos1;

	if (R - L - 1 > D && L != V && R != V) {
		S--;
		if (R - V - 1 <= D) S -= R - V - 1;
		if (V - L - 1 <= D) S -= V - L - 1;
	}
}

vector<long long> solve(long long T) {
	vector<long long>J;
	State.clear(); S = 0;
	State.insert(-(1LL << 60));
	State.insert((1LL << 60));
	for (int i = 0; i <= W; i++) G[i].clear();
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < T; j++) {
			add(A[i] - 1 + (H*W) * 1LL * j);
		}
	}
	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < T; j++) {
			add((B1[i] - 1)*W + (B2[i] - 1) + (H*W) * 1LL * j);
		}
		G[B2[i] - 1].push_back(B1[i] - 1);
	}
	for (int i = 1; i <= W; i++) {
		J.push_back(S);
		for (int j = 1; j <= N; j++) {
			for (int k = 0; k < T; k++) {
				lose(A[j] - 1 + (H*W) * 1LL * k + i - 1);
				add(A[j] - 1 + (H*W) * 1LL * k + i);
			}
		}
		for (int j = 0; j < G[i - 1].size(); j++) {
			for (int k = 0; k < T; k++) {
				lose(G[i - 1][j] * W + (i - 1) + (H*W) * 1LL * k);
				add(G[i - 1][j] * W + W + (i - 1) + (H*W) * 1LL * k);
			}
		}
	}
	return J;
}

int main() {
	cin >> H >> W >> N >> M >> D; //assert(N == 0);
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i <= M; i++) cin >> B1[i] >> B2[i];

	vector<long long>U1 = solve(1);
	for (int i = 0; i < U1.size(); i++) {
		cout << U1[i] << endl;
	}
	return 0;
}

Submission Info

Judge Result