1

Условия Дан массив a длины n, состоящий из чисел от 0 до 106. Требуется отвечать на запросы типа «найдите значение побитового AND всех целых чисел в интервале от l до r включительно».

Напоминаем, что результат побитового AND нескольких чисел — это число, в котором бит равен единице тогда и только тогда, когда во всех этих числах соответствующий бит равен единице.

Система оценки Всего в задаче 20 тестов (не считая примера). Каждый тест оценивается в 5 баллов.

Гарантируется, что не менее, чем в 30% тестов n,q ≤ 1000 и не менее, чем в 30% тестов ai равны 0 или 1.

Формат входных данных Первая строка входных данных содержит два целых числа n и q (1 ≤ n ≤ 2·105; 1 ≤ q ≤ 2·105) — количество чисел и количество запросов соответственно. Вторая строка содержит массив a, перечисленный слева направо, и содержит n целых чисел ai (0 ≤ ai ≤ 106). Каждая из последующих q строк содержит по два целых числа l и r — границы интервала для очередного запроса (1 ≤ l ≤ r ≤ n).

Формат выходных данных Для каждого запроса в отдельной строке выведите одно целое число — результат ответа на очередной запрос.

Примеры
Входные данные:

5 4
2 5 3 4 1
1 3
4 5
2 5
2 3

Выходные данные:

0
0
0
1

Мой вариант:

from operator import __and__
from functools import reduce
 
n, q = map(int, input().split())
*a, = map(int, input().split())
res = []
for _ in range(q):
    left, right = map(int, input().split())
    res.append(reduce(__and__, a[left-1:right]))
print(*res, sep='\n')
8
  • А что с Вашим вариантом не так? (Напишите это в вопросе) Commented 12 окт. 2022 в 17:20
  • Мне нужно его оптимизировать, чтобы он выполнялся быстрее)
    – Evi
    Commented 12 окт. 2022 в 17:24
  • Я к тому, что вы бы либо тесты предоставили, которые вы не проходите, либо условия его прохождения и текущий результат. Commented 12 окт. 2022 в 17:29
  • 1
    судя по тому, что в 30% тестов в списке есть 0, наверное, можно вместо reduce сделать цикл и при получении 0 его прерывать, ясно, что результат будет 0
    – splash58
    Commented 12 окт. 2022 в 17:49
  • 1
    @Evi , если какой-то из ответов вам помог - поставьте слева от него галочку и при желании проголосуйте за него нажав на стрелку вверх, таким образом Вы сможете отблагодарить автора ответа. Commented 12 окт. 2022 в 20:57

2 ответа 2

3

106 это конечно 106. В каждом числе не более 20 бит. Из всех чисел выделим младший бит:

  2 5 3 4 1 - числа
  0 1 1 0 1 - младшие биты
0 1 1 1 2 2 - количество нулевых младших битов с начала списка

По последнему списку можно вычислить будет ли установлен младший бит в ответе на запрос left, right. Если числа на позициях left - 1 и right равны, то нулей между ними нет, бит надо установить. Иначе его надо сбросить.

Рассуждения повторить для всех двадцати битов. Программа отвечает на любой запрос за 20 операций:

def zero_counts(a, bit):
    c = 0
    yield c
    for v in a:
        if v & bit == 0:
            c += 1
        yield c


n, q = map(int, input().split())
a = tuple(map(int, input().split()))

counts = tuple(tuple(zero_counts(a, 1 << k)) for k in range(20))

for _ in range(q):
    left, right = map(int, input().split())
    print(sum(
        1 << k if counts[k][right] == counts[k][left - 1] else 0
        for k in range(20)
    ))
7
  • До сих пор по, по времени не проходит(
    – Evi
    Commented 13 окт. 2022 в 15:34
  • В моём варианте перемешаны ввод диапазонов и вывод результатов. В некоторых системах тестирования это приводит к замедлению вывода. Введите диапазоны в массив (как было сделано у вас), затем выдайте ответы. Commented 13 окт. 2022 в 16:15
  • Дайте ссылку на тестирующую систему. Commented 13 окт. 2022 в 16:22
  • К сожалению нет возможности отправить ссылку, но если вам это поможет, гарантируется, что не менее, чем в 30% тестов n,q ≤ 1000 и не менее, чем в 30% тестов ai равны 0 или 1.
    – Evi
    Commented 13 окт. 2022 в 16:48
  • Попробуйте сами переупорядочить ввод/вывод, напишите сюда комментарий. Commented 13 окт. 2022 в 16:51
1

можно

  1. самому в цикле вычислять and:

     res &= value
    
  2. на каждом шаге проверять равен ли результат 0 и если равен - прервать цикл, поскольку уже 0 никак не изменится

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.