فهرست مندرجات
Distance
یک جدول $n m$ به شما داده شده است که خانه‌های آن به صورت جفت‌های $( 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 انجام داد. توجه کنید که ما قبل از محاسبه آن‌ها می‌دانیم که چه داده‌هایی را احتیاج داریم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
