Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Dopsa
- Как, это опять Вы?
Студентка Катя молча потупила взор.
- И что, у Вас прибавилось знаний с прошлого раза?
- Я учииилааа...
- Что именно Вы учили, Екатерина?
- Массиииивыыыы...
- Хорошо, вот Вам задачка. Есть массив из n элементов, заполненный целыми числами.
И есть m пар индексов Li и Ri, для каждой пары надо определить,
можно ли переставить элементы массива таким образом, чтобы сумма элементов с
Li-го по Ri-й равнялась заданному числу.
- Слооожнооо...
- Ну хорошо, упростим... чтобы сумма равнялась нулю.
- Всё равно слооожнооо...
- Хорошо упростим ещё: элементы массива равны либо 1, либо -1.
- Так ещё сложнее... там числа отрицааательные...
Положите конец страданиям Кати и напишите за неё программу.
Входные данные: В первой строке записаны целые числа n и m (1≤n, m≤100000).
Во второй строке записаны n целых чисел, разделённых пробелами, каждое из которых
равно либо 1, либо -1. В следующих m строках "вопросы", пары индексов, задающие интервалы. В i-той строке записаны целые числа
Li и Ri (1≤Li≤Ri≤n).
Выходные данные: m целых чисел — ответы на вопросы в порядке их следования во входных данных,
по одному в строке. Число 1 означает, что перестановка возможна, 0 - что невозможна.
Для отправки решений необходимо выполнить вход.
|