| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT133B - Bể cá |
Một bể cá 2D có gồm N-1 cột, và lề của mỗi cột được đánh dấu tọa độ. Lề trái của cột đầu tiên có hoành độ là 0, lề phải của cột ngoài cùng bên phải có hoành độ là N.
Trong lòng bể cá được xây dựng các hòn đảo. Với mỗi i (0 ≤ i ≤ N), H_i là độ cao của vùng đảo so với mặt nền.
Khi mực nước dâng lên tới độ cao h, các vùng đất thấp hơn mặt nước sẽ bị ngập. Nhiệm vụ của bạn là tính xem có bể cá đang chứa bao nhiêu đơn vị nước?
Input
Dòng đầu tiên gồm 2 số N và M. (3 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000), trong đó M là số yêu cầu cần thực hiện.
Dòng thứ 2 gồm N số H_i là độ cao của vùng đất tại tại hoành độ i. (0 ≤ H_i ≤ 1000).
M dòng sau, mỗi dòng là 1 query, có 2 dạng như sau:
*) Q h: Độ cao của mực nước trong bể cá là h và yêu cầu tính toán số lượng nước đang có trong bể cá (0 ≤ h ≤ 1000).
*) U i h: Thay đổi độ cao của vùng đất tại hoành độ i thành H_i = h (0 ≤ h ≤ 1000).
Output
Với mỗi query dạng 1, hãy in ra đáp số của bài toán, làm tròn đến 3 chữ số sau dấu phảy (sai số không quá 10-3).
Example
Input:
Test 1:3 2
20 20 20
Q 20
Q 30
Test 2:3 5
0 2 0
Q 2
U 1 1
Q 1
U 1 10
Q 5
Test 3:
7 7
0 2 1 3 2 1 0
Q 1
Q 2
Q 3
U 3 0
Q 1
Q 2
Q 3
Output:
Test 1:0.000
20.000
Test 2:2.000
1.000
2.500
Test 3:0.750
3.750
9.000
1.500
6.000
12.000
Hình minh họa cho test 3, trường hợp h = 2 trước và sau khi update.
| Được gửi lên bởi: | adm |
| Ngày: | 2013-02-08 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
