VMLSEQ - Dãy số may mắn
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Công ty XYZ có m nhân viên. Gần tết công ty quyết định tố chức trò chơi cho các nhân viên của mình. Trò chơi chuẩn bị trước 1 dãy số N số và M yêu cầu. Mỗi nhân viên tham gia trò đều được cho một yêu cầu là chọn tùy ý 1 dãy liên tiếp các số trong đoạn từ L tới R rồi sau đó đưa cho ban tổ chức để nhận thưởng. Với tiêu chí vui là chính nên ai cũng sẽ có mức thưởng ban đầu như nhau. Tuy nhiên những ai chọn được một dãy số may mắn thì sẽ được thưởng nhiều hơn. Phần thưởng cho nhân viên nào chọn trúng được dãy số may mắn có giá trị là X đơn vị tiền tệ trong đó X là độ dài dãy số may mắn mà nhân viên đó chọn được. Để chuẩn bị phần thưởng ban tổ chức muốn biết với mỗi yêu cầu thì phần thưởng có giá trị lớn nhất là bao nhiêu.
Dãy số được gọi là may mắn nếu thỏa mãn tất cả các điều kiện sau:
Dãy số {x, -x} được gọi là dãy số may mắn.
Dãy số {x, S, -x} được gọi là dãy số may mắn nếu S là dãy số may mắn.
Dãy số {S1, S2} được gọi là dãy số may mắn nếu S1 và S2 là 2 dãy số may mắn.
Vì quá bận cho khâu trang trí công ty cho dịp Tết sắp tới nên ban tổ chức đã nhờ đến các coder VNOI giúp đỡ.
Input
- Dòng đầu tiên chứa 2 số nguyên dương N, M.
- Dòng thứ 2 chứa N số miêu tả dãy số được chuẩn bị trước của trò chơi.
- Dòng thứ i trong M dòng tiếp theo chứa 2 số L i , R i miêu tả yêu cầu của nhân viên thứ i.
Output
Dòng thứ i trong M dòng là kết quả cho yêu cầu của nhân viên thứ i.
Giới hạn
- 1 ≤ N, M ≤ 200000
- Các số được chuẩn bị trước là các số nguyên khác 0 và có giá trị tuyệt đối không vượt quá 10 5
- 1 ≤ L i ≤ R i ≤ N
- 30% số test có N, M ≤ 1000
Example
Input: 10 2 2 1 -1 -2 5 1 -1 7 -7 5 1 7 7 10 Output: 4 2
- Người up: voj
- Nguồn bài: VNOI Marathon 2014 - Trần Phan Anh Khoa