Hình chữ nhật giao nhau (DUTPC'21)

View as PDF

Submit solution

Points: 500 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

Cho một lưới hình vuông kích thước 10^9*10^9 được chia làm các hình vuông nhỏ kích thước 1*1. Các hàng của lưới hình vuông đánh số từ 1 đến 10^9 từ trên xuống và các cột đánh số từ 1 đến 10^9 từ trái qua phải. Ô nằm trên giao của hàng i và cột j gọi là ô (i,j).
n hình chữ nhật và có cạnh song song với lưới và nằm trong lưới hình vuông trên. Hình chữ nhật thứ i có góc trên bên trái là ô (a_i,b_i) và ô ở góc dưới bên phải là ô (c_i,d_i).

Hai hình chữ nhật được gọi là giao nhau nếu chúng có chung ít nhất một ô. Hãy đếm số lượng các cặp hình chữ nhật (u,v) với (1≤u<v≤n) mà hình chữ nhật thứ u và hình chữ nhật thứ v giao nhau.

Dữ liệu vào:

  • Dòng đầu chứa số nguyên T≤ 1000 là số bộ dữ liệu.
  • Với mỗi bộ dữ liệu:
    • Dòng đầu chứa số nguyên n≤2*10^5.
    • n dòng tiếp theo, dòng thứ i chứa bốn số nguyên a_i,b_i,c_i,d_i cách nhau bởi những dấu cách (1≤a_i≤c_i≤10^9;1≤b_i≤d_i≤10^9 ).
  • Tổng các giá trị n trong tất cả các test không vượt quá 2*10^5.

Dữ liệu ra:

  • In ra T dòng, ứng với T bộ dữ liệu, in ra số lượng các cặp hình chữ nhật (u,v) với (1≤u<v≤n) mà hình chữ nhật thứ u và hình chữ nhật thứ v giao nhau.

Input

2
2
1 1 2 2
2 2 3 4
3
2 1 4 4
4 2 5 5
1 4 4 6

Output

1
3

Giải thích

Test ví dụ 1:

có 1 cặp hình giao nhau (1, 2).

Test ví dụ 2:

có 3 cặp hình giao nhau: (1, 2), (1, 3), (2, 3).


Nguồn: DUTPC 2021


Be the first to comment

Comments

There are no comments at the moment.