−فهرست مندرجات
Distance
یک جدول nm به شما داده شده است که خانه‌های آن به صورت جفت‌های ( 1 \leq i \leq n ,1 \leq j \leq m) شماره‌گذاری شده‌اند. فاصله‌ي دو خانه (i_1,j_1) و (i_2,j_2) برابر است با |i_1-i_2| + |j_1-j_2|. تعدادی از خانه‌های جدول سیاه‌اند.
به شما تعدادی جفت خانه (y_i,y_j) و (x_i,x_j) داده شده است، شما باید به ازای هر جفت خانه (x,y) تعداد خانه‌های سیاهی که به x نزدیک تراند و تعداد خانه‌های سیاهی که به y نزدیک تراند و تعداد خانه‌های سیاهی که فاصله برابر از x و y دارند را به دست آورید.
ورودی
در سطر اول ورودی چهار عدد (1 \leq n,m \leq 10^9) و (1 \leq p,q \leq 10^5) آمده است. در p سطر بعدی (i,j) خانه‌های سیاه آمده است. در q سطر آخر ورودی در هر سطر چهار عدد x_i و x_j و y_i و y_j به ترتیب آمده‌اند که مختصات دو خانه x و y را مشخص می کنند.
خروجی
در هر کدام از q سطر خروجی سه عدد چاپ کنید که عدد اول تعداد خانه‌های سیاه نزدیک تر به x است، عدد دوم تعداد خانه‌های نزدیک تر به y و عدد آخر تعداد خانه‌هایی است که فاصله برابر از x و y دارند.
محدودیت‌ها
- محدودیت زمان: ۶ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودي و خروجي نمونه
| ورودي نمونه | خروجي نمونه |
|---|---|
| 6 5 6 1 1 2 6 5 5 1 3 3 3 4 4 1 2 3 4 3 | 1 3 2 |
پاسخ
فرض کنید که مقدار sq(i,j) برابر باشد با تعداد خانه‌های سیاه (x,y) که x \leq i و y \leq j برقرار باشد. همچنین مقدار l_1(i,j) برابر باشد با تعداد خانه‌های سیاهی که دو شرط x \leq i و x+y \leq i+j را دارند و مقدار l_2(i,j) برابر با تعداد خانه‌های سیاهی باشد که دو شرط x \leq i و x-y \leq i-j را دارند.
می‌توان نشان داد که که اگر دو خانه x و y در نظر بگیریم ، می‌توان تعداد خانه‌هایی که به هر کدام از آن ها نزدیک تراند را به صورت عبارتی بر حسب تعداد محدودی از sq ها و l_1 ها و l_2 ها بنویسیم. در ابتدا این مقادیر را محاسبه نمی‌کنیم و پس از این که برای تمام جفت خانه‌های x و y پاسخ سؤال را بر حسب توابع گفته شده محاسبه کردیم، شروع به محاسبه مقادیر می‌کنیم و پاسخ دقیق در خواست‌ها را به‌دست می‌آوریم.
محاسبه مقدار دقیق sq ها l_1 ها و l_2 ها را می‌توان به صورت مشابه و با استفاده از الگوریتم sweep line و با استفاده از داده ساختار segment tree انجام داد. توجه کنید که ما قبل از محاسبه آن‌ها می‌دانیم که چه داده‌هایی را احتیاج داریم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
