| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P175PROD - ROUND 5D - Sự kiện lịch sử 2 |
Nhờ sự giúp đỡ của các Coder nên Ryze đã hoàn thành bài tập của cô giáo một cách nhanh chóng. Lần này cô giáo Fiora quyết định cho cậu một bài tập khó hơn, các bạn hãy giúp Ryze giải quyết bài tập này:
Lịch sử thế giới bao gồm đúng N sự kiện. Sự kiện thứ i được bắt đầu từ năm ai và kết thúc vào năm bi (ai < bi). Cô cho rằng sự kiện j chứa đựng sự kiện i nếu aj < ai và bj > bi. Đối với mỗi sự kiện lịch sử hãy đếm số sự kiện lịch sử mà nó chứa.
Input
Dòng đầu chứa số nguyên N (1 <= N <= 2 x 10^5) là số sự kiện xảy ra trong lịch sử.
N dòng tiếp theo, dòng thứ i + 1 chứa 2 số nguyên ai và bi(-10^9 <= ai < bi <= 10^9) là năm bắt đầu và kết thúc của sự kiện thứ i (ai, bi, aj, bj khác nhau đôi một với mọi i, j (i!=j)).
Output
In trên n dòng, dòng thứ i chứa số nguyên duy nhất là số sự kiện lịch sử mà sự kiện thứ i chứa.
Example
Input:
4
-1 9
4 5
2 7
0 1
Output:
3
0
1
0
| Được gửi lên bởi: | adm |
| Ngày: | 2017-03-17 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
