trang chủ / đề bài / icpc19_nat_k

Vương quốc Kiến

Đề bài

Mô tả

Kiến Chimera đang xây dựng vương quốc của riêng mình!

Có n con kiến được đánh số từ 1 đến n. Mỗi con kiến phụ trách việc xây dựng vương quốc trong một vùng hình chữ nhật. Cụ thể, con kiến thứ i được giao một vùng hình chữ nhật trên mặt phẳng tọa độ, có các cạnh song song với hai trục tọa độ và hai đỉnh đối diện là (xi,yi) và (ui,vi).

Một số vùng, hoặc một phần của một số vùng, có thể được giao cho nhiều con kiến. Thông thường điều này không gây vấn đề gì: khi hai con kiến bất đồng ý kiến, mọi con kiến được giao vùng đó sẽ bỏ phiếu cho hai phương án, và phương án nhiều phiếu hơn sẽ được thực hiện. Tuy nhiên, cách này không dùng được nếu một vùng được giao cho một số chẵn khác 0 con kiến, vì kết quả bỏ phiếu có thể hòa. Đàn kiến muốn biết tổng diện tích của những vùng như vậy. Hãy giúp chúng!

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n (1≤n≤105).

Dòng thứ i trong n dòng tiếp theo chứa 4 số nguyên xi,yi,ui,vi (−109≤xi,yi,ui,vi≤109): (xi,yi) và (ui,vi) là tọa độ hai đỉnh đối diện của vùng hình chữ nhật giao cho con kiến thứ i.

Lưu ý các vùng hình chữ nhật có thể có diện tích bằng 0.

Dữ liệu ra

In ra một số nguyên là tổng diện tích các phần được giao cho một số chẵn dương con kiến.

Ràng buộc

  • 1≤n≤105
  • −109≤xi,yi,ui,vi≤109

Ví dụ

Input Output Giải thích
2
10 10 20 20
15 15 25 30
25 Hai hình chữ nhật [10,20]×[10,20] và [15,25]×[15,30] giao nhau ở hình vuông [15,20]×[15,20], được giao cho 2 con kiến; diện tích là 25.
3
0 0 4 4
2 2 6 6
1 1 3 5
7 Ví dụ bổ sung (không có trong đề gốc). Phần được giao cho đúng 2 con kiến có diện tích 7; ô [2,3]×[2,4] (diện tích 2) được giao cho 3 con kiến nên không tính.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0