- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
نقشه شازززلند به شکل یک مستطیل $A×B$ است. که گوشههای مقابلش $(0 ,0)$ و $(A, B)$ هستند.
شازززلند $n$ شهر دارد که شهر $i$ام در مختصات $(x_i, y_i)$ قرار دارد.
به شهر $i$ میگوییم غربی اگر و تنها اگر $x_i = 0$ باشد.
و به آن میگوییم شرقی اگر و تنها اگر $x_i = A$ باشد.
شهرها به وسیله $m$ جاده به هم وصل شدهاند. جادهها به شکل خطهای مستقیم در نقشه از یک شهر به شهر دیگری هستند. جادهها یا یک طرفهاند یا دو طرفه.
هیچ دو جادهای همدیگر را قطع نمیکنند. یعنی خطهایشان نقطه مشترک ندارند، مگر در شهرها.
شهردار شازززلند نقشه شازززلند را به شما داده و از شما میخواهد که به ازای هر شهر غربی پیدا کنید که به چند شهر شرقی مسیر دارد.
ورودی
در خط اول ورودی اعداد $n$ و $m$ و $A$ و $B$ آمدهاند. $$1 \le n \le 300,000$$$$0 \le m \le 900,000$$$$1 \le A, B \le 10^9$$
در خط $i$ ام از $n$ خط بعدی $x_i$ و $y_i$ آمدهاند. $$0 \le x_i \le A$$$$0 \le y_i \le B$$
در خط $i$ ام از $m$ خط بعدی $c_i$ و $d_i$ و $k_i$ آمدهاند. $$1 \le c_i, d_i \le n$$$$1 \le k \le 2$$
اگر $k_i = 1$، جادهای یک طرفه از شهر $c_i$ به شهر $d_i$ وجود دارد. در غیر این صورت، جاده ای دو طرفه بین شهر $c_i$ و $d_i$ وجود دارد. هیچ جادهای بیشتر از یکبار در ورودی نیامده است.
میتوانید فرض کنید حداقل یک راس غربی وجود دارد که به حداقل یک راس شرقی مسیر دارد.
خروجی
باید به ازای هر شهر غربی چاپ کنید به چند شهر شرقی مسیر دارد. خروجی باید به ترتیب نزولی مختصات $y$ نقطهها باشد. یعنی برای بالاترین شهر غربی در خط اول خروجی دومین بالا ترین شهر غربی در خط دوم خروجی و...
زیرمسئلهها
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۳۰ | $$ n, m \le 6000 $$ |
۲ | ۷۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
5 3 1 3
0 0
0 1
0 2
1 0
1 1
1 4 1
1 5 2
3 5 2
خروجی نمونه ۱
2
0
2
ورودی نمونه ۲
12 13 7 9
0 1
0 3
2 2
5 2
7 1
7 4
7 6
7 7
3 5
0 5
0 9
3 9
1 3 2
3 2 1
3 4 1
4 5 1
5 6 1
9 3 1
9 4 1
9 7 1
9 12 2
10 9 1
11 12 1
12 8 1
12 10 1
خروجی نمونه ۲
4
4
0
2
- شهر در مختصات $ (0, 9)$ به $4$ شهر شرقی مسیر دارد.
- شهر در مختصات $ (0, 5)$ به $4$ شهر شرقی مسیر دارد.
- شهر در مختصات $ (0, 3)$ به $0$ شهر شرقی مسیر دارد.
- شهر در مختصات $ (0, 1)$ به $2$ شهر شرقی مسیر دارد.
ارسال پاسخ برای این سؤال