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

EDYOOCATIONAL CONTESNT #2
Автор mahmoud_osama08, история, 6 недель назад, По-английски

Today we teach the ability to perform range queries in $$$\mathcal{O}(1)$$$, regardless of the query rekwaired.

Consider $$$Q = [l, r]$$$.

Iterate over all quadraubles $$$\left(a,b,c,d\right)$$$, add $$$Q[a]\times Q[b]\times Q[c] - Q[d]^2$$$

Now to solve single qwery, output $$$\text{Quadruble}[l][r^2][r-l^r][l+r^l]$$$.

The precomputation took $$$\mathcal{O}(1)$$$ time because $$$a,b,c,d\le 10^{18}$$$, a constant

You solve every query in $$$\mathcal{O}(1)$$$ cuz u immediately output the formula.

if you dont trust me, try it in this problem

you can see that my code is fastest ($$$0.00$$$ s)

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

»
6 недель назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Get a life.

→ Ответить
»
6 недель назад, # |
← Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

The following sieve is O(1) time fr

bool composite[100'001]; 
int main () {
   for (int i = 2; i * i <= 100'000; i++) {
      if (!composite[i]) {
         for (int j = 2 * i; j <= 100'000; j += i) composite[j] = 1;
      }
   }
}
→ Ответить
»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

One can process everything that the program might receive in "O(1)" time since it's always bounded. How to process it is an another story.

→ Ответить