TLEoj Contest #07 - Truy vấn hình vuông

Điểm: 800 (thành phần)

Thời gian: 1.0s

Python 3 2.0s

Bộ nhớ: 256M

Python 3 512M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight

Dạng bài

Trên mặt phẳng tọa độ $Oxy$ trống, bạn được cho $q$ truy vấn, truy vấn thứ $i$ yêu cầu bạn phủ một hình vuông có độ dài cạnh $1$ lên mặt phẳng sao cho vị trí góc trái dưới của hình vuông nằm ở tọa độ $(u, v)$ (và hiển nhiên góc phải trên của hình vuông nằm ở tọa độ $(u + 1, v + 1)$ ), đồng thời yêu cầu bạn tính tổng chu vi của phần được phủ bởi các hình vuông.

Input, Output và Subtasks

Input: (bàn phím)

Dòng đầu tiên gồm số nguyên dương $q$ $(q \le 10^5)$ - số truy vấn bạn cần thực hiện.
$q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u_i, v_i$ $(1 \le u_i, v_i \le 5000)$ mô tả các truy vấn cần thực hiện. Dữ liệu đầu vào đảm bảo $(u_i, v_i) \neq (u_j, v_j)$ với mọi $i \neq j$ .

Output: (màn hình)

Vỡi mỗi truy vấn, in ra tổng chu vi của phần được phủ bởi các hình vuông trên một dòng.

Subtasks

$30\%$ số điểm có $q \le 200; x_i, y_i \le 50$ .
$30\%$ số điểm có $q \le 5000; x_i, y_i \le 500$ .
$40\%$ số điểm còn lại không có giới hạn gì thêm.

Sample

Input (bàn phím)

Output (màn hình)

Notes

Sau truy vấn thứ nhất, chu vi của phần được phủ là $4$ .
Sau truy vấn thứ hai, chu vi của phần được phủ là $8$ .
Sau truy vấn thứ ba, chu vi của phần được phủ là $8$ .

Bình luận

Không có bình luận nào.