A data structure to do a specific lookup fast
Using SSE2 operations, you can save the entire dataset in 512 KB and search through it, with 4-core CPU, is less than 10 microseconds.

PCMPB+PMOVMSKB instructions will give you 16-bit mask made from 16 byte-wide comparisons. You need to combine two such masks as a&lt;&lt;16+b and make sure that result is all 0s.



Even faster approach is to make bitmap for each p[i]&lt;k condition, overall you need 30*6=180 bitmaps. Each bitmap takes 30K/8=3.75 KB, overall 675 KB.

You need to AND-combine 30 maps corresponding to chosen x[i], i.e. AND-process 675/6=112.5 KB of data. With 128-bit SSE operations, this requires 7K operations, and on the same 4-core CPU, it's less than microsecond long.