VM 15 Bài 11 - Các hình Ellipse

View as PDF

Submit solution

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

Problem source:
VM - KrK
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

KrK có một trò chơi vô cùng thú vị cùng với các hình ellipse của mình. Mỗi hình Ellipse được đặc trưng bởi ~2~ con số nguyên dương là bán trục lớn ~a~ và bán trục nhỏ ~b~.

KrK có ~N~ hình Ellipse đặt trên mặt bàn, các hình ellipse được đánh số lần lượt từ ~1~ đến ~N~. Cặp số ~A~ và ~B~ được gọi là chỉ số hoàn hảo của hình Ellipse. Nếu với ellipse thứ ~i~ có ~a_{i} > A~ hoặc ~b_{i} > B~ thì hình ellipse đó được coi là không đẹp và sẽ biến mất khỏi mặt bàn (và không bao giờ trở lại). Và tất nhiên với hình ellipse nào mà có ~a_{i} \leq 0~ hoặc ~b_{i} \leq 0~ cũng sẽ biến mất khỏi mặt bàn (và không bao giờ trở lại). KrK có ~M~ truy vấn dành cho bạn như sau:

  • Loại ~1~: Cho ~3~ số nguyên ~l~, ~r~ và ~v~, bạn cần đặt ~a_i = v~, với ~i~ thuộc đoạn [~l~, ~r~].
  • Loại ~2~: Cho ~3~ số nguyên ~l~, ~r~ và ~v~, bạn cần đặt ~b_i = v~, với ~i~ thuộc đoạn [~l~, ~r~].
  • Loại ~3~: Cho ~3~ số nguyên ~l~, ~r~ và ~v~, bạn cần đặt ~a_i = a_{i} + v~, với ~i~ thuộc đoạn [~l~, ~r~].
  • Loại ~4~: Cho ~3~ số nguyên ~l~, ~r~ và ~v~, bạn cần đặt ~b_i = b_{i} + v~, với ~i~ thuộc đoạn [~l~, ~r~].
  • Loại ~5~: Cho ~l~ và ~r~, bạn cần in ra tổng diện tích các hình ellipse trong đoạn từ ~l~ đến ~r~ chia cho ~\pi~ (pi). Nếu hình ellipse trong đoạn [~l~, ~r~] không còn nằm trên bàn nữa thì diện tích của nó bằng ~0~.
  • Loại ~6~: Cho ~l~ và ~r~, bạn cần in ra số lượng các hình ellipse còn nằm trên mặt bàn trong đoạn từ ~l~ đến ~r~.

Input

Dòng đầu tiên chứa ~2~ số nguyên dương ~N~ và ~M~ -- Số lượng hình ellipse ban đầu và số lượng truy vấn.

Dòng tiếp theo chứa ~2N~ số nguyên, cặp thứ ~i~ miêu tả bán trục lớn ~a_i~ và bán trục nhỏ ~b_i~ của hình ellipse thứ ~i~.

~M~ dòng tiếp theo miêu tả các truy vấn KrK đề ra với định dạng sau ~t~, ~l~, ~r~ và ~v~ (nếu có) ~(1 \leq t \leq 6~, ~1 \leq l \leq r \leq N)~ -- với ~t~ là loại của truy vấn như đã miêu tả ở trên.

Dòng cuối cùng chứa ~2~ số nguyên dương ~A~ và ~B~ (Chỉ số hoàn hảo)

Output

Với mỗi truy vấn loại ~5~ và ~6~ in ra kết quả tương ứng ở mỗi dòng riêng biệt theo thứ tự.

Giới hạn

  • ~1 \leq N~, ~M \leq 10^{5}~
  • ~1 \leq a~, ~b \leq 10^{6}~
  • ~-10^{6} \leq v \leq 10^{6}~
  • ~1 \leq A~, ~B \leq 10^{6}~
  • Trong ~20\%~ số test, ~N, M \leq 1000.~

Sample Input

1 3
1 1
6 1 1 
3 1 1 1 
6 1 1
1 1

Sample Output

1
0

Comments

Please read the guidelines before commenting.


There are no comments at the moment.