English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mse06h

Japan chuẩn bị chào đón ACM ICPC World Finals và muốn xây 1 số đường. Japan là 1 hòn đảo với N thành phố ở bờ phía Đông và M thành phần ở bờ phía Tây, (M ≤ 1000, N ≤ 1000). Các thành phố ở mỗi bờ được đánh số từ 1 trở đi theo chiều từ Bắc tới Nam. K superhighways sẽ được xây để nối bờ phía Đông và bờ phía Tây của Japan. Mỗi superhighway là 1 đường thẳng nối 1 thành phố ở bờ Đông và 1 thành phố ở bờ Tây.

Xác định số giao điểm của các đường cao tốc này. Không có 3 đường cao tốc cắt nhau tại 1 điểm.

Dòng đầu của file Input là T - số test. Mỗi test bắt đầu bởi 3 số – N, M, K. Tiếp theo là K dòng, mỗi dòng 2 số mô tả cặp thành phố được nối bởi đường cao tốc (số thứ nhất ở bờ Đông, số thứ hai ở bờ Tây)

Với mỗi test case, in ra 1 dòng có dạng :

Test case "case number": "số giao điểm"

Chu y : khong co dau cach nao giua "case number" va dau ":" dau nhe, ko thi ban se ko hieu tai sao ko AC.

Sample

Input :
1 
3 4 4 
1 4 
2 3 
3 2 
3 1 
Ouput: 
Test case 1: 5

---

hide comments

	androidbasha: 2023-07-18 14:32:52 You can Solve it Using BIT (Fenwick Tree). Just Iterate over Cities (n) and each time see how many Cities from East (m) Comes After You