Tháng tư là lời nói dối của nqson


Submit solution

Points: 4
Time limit: 2.0s
Memory limit: 977M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

nqson vừa phát minh ra máy kiểm tra nói dối, kiểm tra mức độ chân thật trong một câu nói. Nếu đó là lời nói thật, máy sẽ cho ra kết quả là 1 số dương, ngược lại nếu đó là lời nói dối, máy sẽ cho ra kết quả là 1 số âm. Kết quả càng lớn thì mức độ chân thật của câu nói ấy càng cao.

Ví dụ: Khi nqson nói "Trái đất hình cầu", máy sẽ cho ra kết quả 12345678 tức câu nói này là 1 câu cực kỳ hiển nhiên. Còn khi nqson nói "I love nqson", máy sẽ ra kết quả -12345 tức nqson có khả năng đang nói dối.

Trong tháng tư, nqson đã nói dối rất nhiều câu để kiểm tra, sửa chữa và nâng cấp máy. Nhằm thuận tiện cho việc nghiên cứu, nqson muốn thống kê xem: Từ câu nói thứ \(x\) đến câu nói thứ \(y\), có bao nhiêu câu nói có mức độ chân thật nằm trong đoạn \([l, r]\).

Đầu vào

Dòng đầu chứa 2 số tự nhiên \(n\) là số câu nói của nqson và \(m\) là số lần nqson thống kê

Dòng thứ hai chứa \(n\) số nguyên \(a_i\) là kết quả từng câu nói mà máy đã kiểm tra

\(m\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(x, y, l, r\)

Đầu ra

\(m\) dòng, mỗi dòng chứa một số nguyên là kết quả của từng lần thống kê

Giới hạn

\(1 \le n,m \le 10^5\)

\(-10^9 \le a_i \le 10^9\)

\(1 \le x \le y \le n\)

\(-10^9 \le l \le r \le 10^9\)

Ví dụ

Đầu vào

8 3
1 5 2 -1 -10 2 -9 0
2 7 -1 1
2 3 0 8
1 8 -20 0

Đầu ra

1
2
4

Comments