P145SUMB spoj PTIT – ROUND 5B – Sắp xếp

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P145SUMB/

1. Đề bài P145SUMB spoj

Bạn có một mảng a[] gồm n phần tử, đánh số từ 1 tới n, mỗi phần tử có giá trị -1 hoặc 1.

Bạn cần phải trả lời m truy vấn. Truy vấn thứ i dạng L[i], R[i] (1 <= L[i] <= R[i] <= n), hỏi rằng liệu có cách nào để sắp xếp lại mảng a[] để a[L[i]] + a[L[i] +1] + … + a[R[i]] = 0.

Input

Dòng đầu tiên gồm 2 số nguyên n, m (1 <= n, m <= 2.10^5).

Dòng tiếp theo gồm n số của mảng a[].

m dòng tiếp theo là m truy vấn. Dòng thứ i chứa 2 số nguyên L[i], R[i] là truy vấn i.

Output

m dòng trả lời cho các truy vấn. Với mỗi truy vấn, n ra 1 nếu có, ngược lại in ra 0.

Example

Test 1:

Input:

2 3

1 -1

1 1

1 2

2 2

Output:

0

1

0

 

Test 2:

Input:

5 5

-1 1 1 1 -1

1 1

2 3

3 5

2 5

1 5

Output:

0

1

0

1

0

2. Code tham khảo p145SUMB

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *