Sử dụng Binary Index Tree (BIT): Gọi điểm của một người là x và y, sort theo x, nếu x bằng nhau thì sort theo y. Sau đó duyệt từng nhóm người có cùng điểm cả x và y, dùng BIT lấy số lượng người thua những người trong nhóm này, sau đó update toàn bộ nhóm người này trên BIT.
Problem
https://vn.spoj.com/problems/CRATE
https://oj.vnoi.info/problem/CRATE
Cho danh sách N lập trình viên (1 ≤ N ≤ 300000), đánh số lần lượt từ 1 đến N. Mỗi người đều tham gia cả hai giải thi đấu: Giải THPT và giải Mở rộng. Với mỗi lập trình viên, bạn sẽ được cung cấp điểm số của giải Mở rộng Ai và điểm số của giải THPT Hi (Các điểm số đều là số nguyên không âm và không vượt quá 100000). Lập trình viên i được coi là giỏi hơn lập trình viên j khi và chỉ khi cả 2 điểm số của lập trình viên i đều lớn hơn hoặc bằng điểm số tương ứng của lập trình viên j, trong đó có ít nhất 1 điểm số phải lớn hơn. Hãy tính xem với mỗi lập trình viên i thì có bao nhiêu lập trình viên mà i giỏi hơn.
Input
Dòng đầu tiên chứa số nguyên N.
N dòng tiếp theo, dòng thứ i+1 chứa 2 số nguyên Ai và Hi.
Output
Dòng i chứa số lượng lập trình viên mà lập trình viên i giỏi hơn.
Example
Input
8
1798 1832
862 700
1075 1089
1568 1557
2575 1984
1033 950
1656 1649
1014 1473
Output
6
0
2
4
7
1
5
1
Tutorial
Submission
CRATE.cpp