MSE06H - Japan

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

Added by:psetter
Date:2009-04-16
Time limit:0.209s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Southeastern European 2006

hide comments
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.