Блог пользователя The_DarkKnight

Автор The_DarkKnight, история, 3 года назад, По-английски

I recently came across a question that reads as follows:

We are given n pairs of number: (a1,b1), (a2,b2)....(an,bn).

We need to find if there exists n numbers : x1,x2...xn such that a_i <= x_i <= b_i and (x1 & x2 & ....xn = 0) where & denotes bitwise and.

Constraints:

1<=n<=10^5

1<=a_i,b_i<=10^9

I thought of check for each bit if it becomes zero in each interval. But that is wrong as two bits can become zero in an interval but not necessarily at the same number.

How to proceed with this?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится