# PROBLEM LINK:

Author: Shahjalal Shohag

Tester: Ildar Gainullin

Editorialist: Rajarshi Basu

# DIFFICULTY:

Easy

# PREREQUISITES:

Observation

# PROBLEM:

You are given an integer sequence A_1, A_2, \ldots, A_N. For any pair of integers (l, r) such that 1 \le l \le r \le N, let’s define \mathrm{OR}(l, r) as A_l \lor A_{l+1} \lor \ldots \lor A_r. Here, \lor is the bitwise OR operator.

In total, there are \frac{N(N+1)}{2} possible pairs (l, r), i.e. \frac{N(N+1)}{2} possible values of \mathrm{OR}(l, r). Determine if all these values are pairwise distinct.

- N \leq 10^5
- 0 \leq A_i \leq 10^{18}

# EXPLANATION:

## Brief Explanation

- If number of elements is more than \log_2 10^{18} \approx 62 then answer is NO.
- Else just bruteforce all possible ranges.

## Some initial thoughts

The question involves bitwise operators. When you see bitwise operators involved, it’s safe to say there might be something to do with … well…

bits. Further, it feels like the number of possible different values ofsubarray ORcannot be too many, and seems to be much lesser than O(n^2) in any case. Maybe this can be explored further?

## What makes a number important

Let us say we have some range of numbers A[L \dots R]. Let us say we add another number, in particular A[R+1] (so our final range is A[L \dots R+1]). When will the OR value of this range be different than the previous A[L \dots R] range? When A[R+1] adds some

right?”new information”

## What is this new information?

Well, this new information is basically some bit i that was

in V_1 = A[L] \vee A[L+1] \vee \dots \vee A[R]. Is this true? What does this mean for the problem? Does it hint towards a solution? Think!not set

## Main Observation

## Part 1

Let there be two indices i and j such that A[i] \vee A[j] = max(A[i],A[j]). You can think of this meaning that all of the bits set in A[j] is also set in A[i], or vice versa, for some i,j. In such a scenario, the solution is not possible. Here’s why.

- Let’s assume that i < j.
- Now consider V_1 = (A[i] \vee A[i+1\ \vee A[i+2] \vee \dots \vee A[j-1]).
- Now consider V_2 = V_1 \vee A[j]
- We know that each bit k set in A[j] is also set in A[i], and therefore in V_1. Thus, from there we get that V_2 = V_1.

How do we utilise this to simplify the problem? Move on to Part 2 if you can’t figure it out.

## Part 2

There are only 62 bits for a number till 10^{18} !!

## Full Solution

- If number of elements is more than \log_2 10^{18} \approx 62 then answer is NO.
- Else just bruteforce all possible ranges.

# SOLUTIONS:

## Setter’s Code

```
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const long long M = 1e18;
long long a[N];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
assert(1 <= t && t <= 300);
int sum = 0;
while (t--) {
int n; cin >> n;
assert(1 <= n && n <= 100000);
sum += n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
assert(0 <= a[i] && a[i] <= M);
}
if (n > 60) {
cout << "NO\n";
continue;
}
set<long long> se;
bool ok = true;
for (int i = 1; i <= n; i++) {
long long cur = 0;
for (int j = i; j <= n; j++) {
cur |= a[j];
if (se.find(cur) != se.end()) {
ok = false;
break;
}
se.insert(cur);
}
if (!ok) break;
}
if (ok) cout << "YES\n";
else cout << "NO\n";
}
assert(1 <= sum && sum <= 300000);
return 0;
}
```

## Tester’s Code

```
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector <ll> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n >= 100) {
cout << "NO\n";
} else {
set <ll> q;
for (int i = 0; i < n; i++) {
ll x = 0;
for (int j = i; j < n; j++) {
x |= a[j];
q.insert(x);
}
}
if (q.size() == n * (n + 1) / 2) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
}
```