Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۲:سوال ۱۹

سوال ۱۹

در هر خانه‌ی یک جدول n×n، یک عدد صحیح با قدر مطلق کم‌تر از ۱۰۰۰ نوشته شده است. در هر Query، یک مستطیل داده می‌شود و برنامه‌ی شما باید عدد مربوط به آن را حساب کند. مستطیل با خانه‌ی بالا و سمت چپش و خانه‌ی پایین و سمت راستش مشخص می‌شود. به عبارت دیگر، اگر aij خانه‌ی ردیف i ام و ستون j ام جدول باشد (که a11 خانه‌ی بالا و سمت چپ جدول است)، مستطیل با i1، j1، i2 و j2 مشخص می‌شود و شامل تمام aij هایی است که i1ii2 و j1jj2. تعداد ستون‌های مستطیل (j2j1+1) عددی زوج می‌باشد. عدد مستطیل عبارت است از جمع عددهای ستون‌های j1، j1+2، j1+4، …، j21 منهای جمع عددهای ستون‌های j1+1، j1+3، j1+5،…، j2 در مستطیل.

ورودی

در سطر اول فایل ورودی دو عدد n و k آمده‌اند، که k تعداد Query ها می‌باشد. سپس جدول نوشته شده است. (n و k به ترتیب از ۱۰۰۰ و 106 بیش‌تر نیستند.)

سپس در k خط، در هر خط اعداد i1، j1، i2 و j2 به ترتیب نوشته شده‌اند.

خروجی

در خروجی k خط بنویسید، به طوری که در خط i ام عدد مستطیل i ام ورودی باشد.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4 2
12 -7 3 5
1 2 0 -2
0 30 17 10
7 3 9 4
1 1 4 4
2 2 3 3
4
15

ابزار صفحه