提出 #74117899

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int h, H, w, W, n, m;
vector <int> vx;
vector <array <int, 4>> event;

struct Node {
	int x, k, t;
} tree[1600010];

inline void update(int id) {
	int l = tree[id * 2].x, r = tree[id * 2 + 1].x;
	tree[id].k = 0;
	if (l <= r) tree[id].k = tree[id * 2].k;
	if (l >= r) tree[id].k += tree[id * 2 + 1].k;
	tree[id].x = min(l, r);
}

inline void settag(int id, int t) {
	tree[id].x += t, tree[id].t += t;
}

inline void pushdown(int id) {
	if (tree[id].t) {
		settag(id * 2, tree[id].t);
		settag(id * 2 + 1, tree[id].t);
		tree[id].t = 0;
	}
}

inline void build(int id, int l, int r) {
	if (l == r) {
		tree[id] = {0, vx[r] - vx[r - 1], 0};
		return;
	}
	int mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	update(id);
}

inline void modify(int id, int l, int r, int ql, int qr, int t) {
	if (l == ql && r == qr) {
		settag(id, t);
		return;
	}
	int mid = (l + r) / 2;
	pushdown(id);
	if (qr <= mid) modify(id * 2, l, mid, ql, qr, t);
	else if (ql > mid)
		modify(id * 2 + 1, mid + 1, r, ql, qr, t);
	else
		modify(id * 2, l, mid, ql, mid, t),
		modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
	update(id);
}

int main() {
	scanf("%d%d%d%d%d", &H, &W, &h, &w, &n);
	if (!n) {
		printf("%lld\n", (H - h + 1) * (W - w + 1LL));
		return 0;
	}
	for (int i = 1, r, c, x1, y1, x2, y2 ; i <= n ; i++) {
		scanf("%d%d", &r, &c);
		x1 = c - w + 1, x2 = c, y1 = r - h + 1, y2 = r;
		x1 = max(x1, 1), y1 = max(y1, 1), x2 = min(x2, W - w + 1) + 1, y2 = min(y2, H - h + 1) + 1;
//		cout << x1 << " " << x2 << " " << y1 << " " << y2 << endl;
		vx.push_back(x1);
		vx.push_back(x2);
		event.push_back({y1, 1, x1, x2});
		event.push_back({y2, -1, x1, x2});
	}
	sort(event.begin(), event.end());
	sort(vx.begin(), vx.end());
	vx.erase(unique(vx.begin(), vx.end()), vx.end());
	m = vx.size() - 1;
	build(1, 1, m);
	int pery = 0, len = tree[1].k;
	ll ans = 0;
	for (auto evt : event) {
		int cov = len;
		if (!tree[1].x) cov = len - tree[1].k;
		ans += ll(evt[0] - pery) * cov;
		int x1 = lower_bound(vx.begin(), vx.end(), evt[2]) - vx.begin() + 1;
		int x2 = lower_bound(vx.begin(), vx.end(), evt[3]) - vx.begin();
		if (x1 > x2) continue;
//		cout << evt[0] << " " << evt[1] << " " << evt[2] << " " << evt[3] << " " << x1 << " " << x2 << " " << ans << endl;
//		cout << tree[1].x << " " << tree[1].k << endl;
		modify(1, 1, m, x1, x2, evt[1]);
		pery = evt[0];
	}
	printf("%lld\n", (H - h + 1) * (W - w + 1LL) - ans);
	return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:61:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   61 |         scanf("%d%d%d%d%d", &H, &W, &h, &w, &n);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:67:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |                 scanf("%d%d", &r, &c);
      |                 ~~~~~^~~~~~~~~~~~~~~~

ジャッジ結果