report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
  • Problem
  • Submit
  • Results
Trick-OR-Treat - MarisaOJ: Marisa Online Judge

Trick-OR-Treat

Time limit: 1000 ms
Memory limit: 256 MB
On that dreaded Halloween night, **Reimu** was trapped inside an ice cage hanging in mid-air by a gang of mischievous spirits. They left a letter for **Cirno**: “Gather ’round, little fairies! If you want to save the **Hakurei Shrine Maiden** from being frozen forever, solve this riddle: Given a sequence $a$ of $n$ magic stones, each holding a power index $a_i$, and a power threshold $x$. Count how many index pairs $(i, j)$ such that $\(i < j\)$ and $a_i \text{ OR } a_j \leq x$. They’ve promised that if **Cirno** answers correctly, they’ll thaw **Reimu** out. Since **Cirno** is busy "trick-or-treating" with **Marisa** and has no time to puzzle it out, please help her! ### Input - The first line consists of two integers $n$ and $x$. - The second line contains $n$ integers $a_i$. ### Output - The total number of pairs $(i, j)$ that satisfies the requirements. ### Constraints - $2 \leq n \leq 5 \times 10^5$. - $1 \leq a_i, x \leq 10^9$. ### Scoring - Subtask 1 (**30%** of points): $2 \leq n \leq 5 \times 10^3$. - Subtask 2 (**30%** of points): $1 \leq a_i \leq 1000$. - Subtask 3 (**40%** of points): No additional constraints. ### Example **Input** ``` 5 15 6 7 69 420 1337 ``` **Output** ``` 1 ```
Bitwise operations
Trick-OR-Treat
Bitwise operations 1
Bitwise operations 2
Bitwise operations 3
XOR pair
Full
Range XOR
Cyclic shift
XOR
XORray
Minimum Xor Pair Query
contest
Wooden sticks
MARISA
Supermarket
That yellow girl not in Mesmerizer
# Announcement
Sweet-colored master path
Trick-OR-Treat
Minecraft was her sweets?
Flowless wells
MST Miko Reimu
Cirno's beloved candies
Subterranean Iridescence
String division
Hotspot
Dictionary
Matching numbers
Arrange flowers
Stolen precious thing
Path counting
Rescue Reisen
Bad Apple!!
Internet provider
Christmas decoration
Chemical reaction
Tree path
Spider web
Topic
Others
Rating 800
Solution (0) Solution