Submission #71318793

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define debug(arg) cout << "[" << #arg << "]: " << arg << endl
#else
#define debug(arg) 42
#endif

using llu = unsigned long long;
using ll = long long;

#define vec vector
#define pb push_back
#define all(n) begin(n), end(n)

void solv() {
	int n; cin >> n;
	vec<vec<int>> mat(2000 + 1, vec<int>(2000 + 1));
	vec<tuple<int, int, int, int>> udlr(n);
	for (auto &[u, d, l, r] : udlr) cin >> u >> d >> l >> r;
	for (auto &[u, d, l, r] : udlr) --u, --d, --l, --r;
	for (auto &[u, d, l, r] : udlr) {
		mat[u][l]++;
		mat[u][r + 1]--;
		mat[d + 1][l]--;
		mat[d + 1][r + 1]++;
	}
	auto get = [&](int x, int y) {
		if (x < 0 || y < 0) return 0;
		return mat[x][y];
	};
	auto cp = [&]() {
		for (int i = 0; i <= 2000; ++i) for (int j = 0; j <= 2000; ++j) mat[i][j] += get(i - 1, j) + get(i, j - 1) - get(i - 1, j - 1);
	};
	cp();
	int base = 0;
	for (int i = 0; i <= 2000; ++i) for (int j = 0; j <= 2000; ++j) {
		auto &v = mat[i][j];
		if (v > 1) v = 0;
		else if (!v && i < 2000 && j < 2000) ++base;
	}
	cp();
	for (auto &[u, d, l, r] : udlr) cout << get(d, r) - get(d, l - 1) - get(u - 1, r) + get(u - 1, l - 1) + base << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) solv();
	return 0;
}

Submission Info

Judge Result