Trên Ninh Tháng 6
Mảng cộng dồn - Cơ bản
Nộp bàiPoint: 100
Cho một dãy số nguyên ~a~ gồm ~n~ ~(1 \le n \le 10^5, 1 \le a_i \le 10^6)~ phần tử và ~q~ ~(1 \le q \le 10^5)~ truy vấn. Mỗi truy vấn có dạng ~l,r~, hãy in ra tổng ~a_l,a_{l+1},..,a_r~.
Input
5 4
1 2 3 4 5
1 2
2 3
1 5
3 4
Output
3
5
15
7
SumLen
Nộp bàiPoint: 100
Cho một dãy ~a~ gồm ~n~ phần tử nguyên không âm.
Hãy đếm số đoạn con liên tiếp ~[l,r]~ của dãy ~a~ sao cho tổng của đoạn con đó bằng độ dài của đoạn, hay ~a_l + a_{l+1} + ... + a_r = r - l + 1~.
Input
- Dòng đầu tiên chứa số nguyên dương ~n~.
- Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.
Output
- In ra số đoạn con thỏa mãn.
Điều kiện
- ~1 \le n \le 2*10^5~.
- ~0 \le a \le 9~.
Subtask
- ~50\%~ số điểm: ~n \le 1000~.
- ~50\%~ số điểm: ~n \le 2*10^5~.
Ví dụ
Input 1:
3
1 2 0
Output 1:
3
Input 2:
5
1 1 0 1 1
Output 2:
6
Tribonacci
Nộp bàiPoint: 100
Do đã quá quen với dãy fibonacci, hôm nay, chúng ta hãy cùng tìm hiểu về dãy tribonacci.
Số tribonacci thứ ~i~ sẽ có công thức truy hồi như sau: ~f[i] = f[i-1] + f[i-2] + f[i-3]~ nếu ~i > 3~, ngược lại ~f[i] = i~ nếu ~i \le 3~.
Cho ~n~ số tribonacci đầu tiên và một số ~k~ (~k \le n~), hay tìm một dãy con bất kì (không nhất thiết phải liên tiếp) của dãy ~n~ số tribonacci này sao cho tổng của các phần tử trong dãy con đó chia hết cho ~k~.
Input
- Gồm một dòng chứa số nguyên dương ~n~ và số nguyên dương ~k~ ~(1 \le k \le n \le 10^5)~
Output
- Dòng đầu in ra số ~q~ là độ dài của dãy con thỏa mãn tìm được, nếu không tồn tại in ra ~-1~.
- Dòng thứ hai in ra ~q~ chỉ số của dãy con tìm được.
- Nếu có nhiều hơn một dãy con thỏa mãn, in ra bất kì kết quả nào.
Subtask
- ~30\%~ số test có ~n \le 20~.
- ~40\%~ số test có ~n \le 2000~.
- ~30\%~ số test còn lại có ~n \le 10^5~.
Sample Test
Input:
5 4
Output:
2
2 4
Giải thích:
- ~5~ phần tử đầu tiên của dãy tribonacci là: 1 2 3 6 11
- Chọn ra phần tử thứ ~2~ và ~4~ có tổng bằng: ~2+6 = 8~ chia hết cho ~4~.
Yuyuko tham ăn
Nộp bàiPoint: 100
Ngày hôm nay có ~n~ gian hàng bán đồ ăn tại lễ hội ở đền Hakurei. Yuyuko ham ăn muốn đi ăn ~q~ lượt, mỗi lượt từ gian hàng ~l~ đến gian hàng ~r~. Với mỗi gian hàng, hãy in ra số lần cô ghé thăm.
Input
- Dòng đầu gồm 2 số ~n, q~.
- ~q~ dòng tiếp theo mỗi dòng thứ ~i~ gồm 2 số ~l_i, r_i~ ~(1 \le l_i \le r_i \le 10^5)~ là lượt đi ăn thứ ~i~.
Output
- In ra ~n~ số ứng với ~n~ cửa hàng là số lần Yuyuko vào gian hàng.
Sample Test
Input:
4 3
1 3
2 4
1 2
Output:
2 3 2 1
UpdOp
Nộp bàiPoint: 100
Cho một dãy ~a~ gồm ~n~ phần tử nguyên không âm và ~q~ thao tác, thao tác thứ ~i~ có dạng ~(l_i,r_i,d_i)~, nghĩa là tăng giá trị của các phần tử trong mảng ~a~ từ vị trí ~l_i~ tới ~r_i~ thêm ~d_i~ đơn vị.
Bạn cần thực hiện ~k~ truy vấn, truy vấn thứ ~i~ có dạng ~(x_i,y_i)~, có nghĩa là thực hiện các thao tác ~x_i,x_{i+1},...,y_i~.
Hãy in ra giá trị của các phần tử trong mảng ~a~ sau khi thực hiện ~k~ truy vấn.
Input
- Dòng đầu tiên chứa ~3~ số nguyên dương ~n,q,k~.
- Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.
- ~q~ dòng sau, dòng thứ ~i~ gồm ~3~ số nguyên dương ~l_i,r_i,d_i~ miêu tả thao tác thứ ~i~.
- ~k~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên dương ~x_i,y_i~ miêu tả truy vấn thứ ~i~.
Output
- Gồm một dòng in ra ~n~ số, số thứ ~i~ là giá trị của phần tử ~a_i~ sau khi thực hiện ~k~ truy vấn.
Điều kiện
- ~1 \le n \le 10^5~.
- ~0 \le a_i,d_i \le 10^5~.
Subtask
- ~50\%~ số điểm: ~n \le 1000~.
- ~50\%~ số điểm: ~n \le 10^5~.
Ví dụ
Input 1:
3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3
Output 1:
9 18 17
Input 2:
4 3 6
1 2 3 4
1 2 1
2 3 2
3 4 4
1 2
1 3
2 3
1 2
1 3
2 3
Output 2:
5 18 31 20
IncLad
Nộp bàiPoint: 100
Cho một dãy ~a~ gồm ~n~ phần tử nguyên không âm.
Có ~q~ truy vấn, mỗi truy vấn có dạng ~l,r,d~, có nghĩa là tăng phần tử thứ ~l~ lên ~d~ đơn vị, phần tử thứ ~l+1~ lên ~2*d~ đơn vị, ..., phần tử thứ ~r~ lên ~(r-l+1)*d~ đơn vị. Nói cách khác, phần tử thứ ~i \in [l,r]~ sẽ được tăng thêm ~(i-l+1)*d~ đơn vị.
Hãy in ra dãy ~a~ sau khi thực hiện đủ ~q~ truy vấn.
Input
- Dòng đầu tiên chứa số nguyên dương ~n~
- Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.
- ~q~ dòng sau, mỗi dòng gồm ~3~ số nguyên ~(l,r,d)~ miêu tả truy vấn.
Output
- Gồm một dòng in ra ~n~ số, số thứ ~i~ là giá trị của phần tử ~a_i~ sau khi thực hiện ~q~ truy vấn.
Điều kiện
- ~1 \le n,q \le 10^6~.
- ~0 \le a_i,d_i \le 10^5~.
Subtask
- ~50\%~ số điểm: ~n \le 1000~.
- ~50\%~ số điểm: ~n \le 10^5~.
Ví dụ
Input 1:
1
10
3
1 1 40
1 1 0
1 1 -15
Output 1:
35
Input 2:
5
1 2 3 4 -5
3
5 5 10
1 5 4
2 3 -1
Output 2:
5 9 13 20 25
SStorm
Nộp bàiPoint: 100
Đất nước Mirinda tươi đẹp được mô tả bằng một ma trận ~n \times m~ ô vuông, ô ở dòng thứ ~i~ từ trên xuống và cột thứ ~j~ từ trái sang gọi là ô ~(i, j)~. Khoảng cách giữa ô ~(x,y)~ với ô ~(i,j)~ là ~|x - i| + |y - j|~. Ô ~(i, j)~ có giá trị tài sản là ~a_{i,j}~.
Do biến đổi khí hậu, những cơn bão ngày một nhiều hơn và mạnh hơn. Mỗi cơn bão được đặc trưng bởi:
- ~w~ - cấp bão,
- ~R_1~ - bán kính bão,
- ~R_2~ - bán kính mắt bão,
- ~(x, y)~ - tọa độ bão sẽ đổ bộ.
Theo đó, các ô ~(i, j)~ có khoảng cách đến ô ~(x, y)~ thuộc đoạn ~[R_2, R_1]~ sẽ bị tác động, đồng thời giá trị tài sản ở ô đó sẽ giảm đi min(w, b[i][j])
, với ~b_{i,j}~ là giá trị tài sản hiện có ở ô ~(i, j)~.
Là một nước giáp biển, hằng năm đất nước Mirinda phải đón ~k~ trận bão. Do đặc trưng địa hình, bão sẽ chỉ đổ bộ vào một trong ~q~ ~(q < 5)~ điểm phân biệt. Rút kinh nghiệm từ siêu bão Fanta, ủy ban chống bão muốn biết sau khi ~k~ trận bão đó tàn phá thì nước này phải chịu tổng thiệt hại là bao nhiêu?
(Tổng thiệt hại của nước này được tính bằng tổng mức giảm giá trị tài sản của tất cả các ô).
Input
- Dòng đầu tiên chứa ~4~ số nguyên dương ~n,m,q,k~ (~1 < n, m < 500, k \leq 10^5~).
- ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên ~a_{i,j}~ (~0 < a_{i,j} < 10^9~).
- Dòng tiếp theo ghi ~2 \times q~ số nguyên là tọa độ của ~q~ điểm đặc biệt: ~x_1, y_1, x_2, y_2, \ldots, x_q, y_q~.
- ~k~ dòng cuối, mỗi dòng ghi ~5~ số nguyên mô tả cơn bão: ~w, R_1, R_2, x, y~ (~0 < R_2 < R_1 < 1000, 0 < w < 1000~). Dữ liệu đảm bảo ~x,y~ là ~1~ trong ~q~ điểm đã cho.
(Các trận bão sẽ được liệt kê theo đúng thứ tự đổ bộ).
Output
In ra tổng thiệt hại sau ~k~ cơn bão.
Sample Test
Input:
3 4 2 4
10 11 12 15
20 10 11 25
30 32 35 40
1 1 3 4
2 2 0 3 4
2 2 0 1 1
2 4 2 1 1
2 3 1 3 4
Output:
56