| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
An ordinary problem with an extraordinary(maybe) complexity! Help needed!
Suppose an array contains n elements. The elements is in the range 109. We want to know, for every element in the array, the position of the leftmost element that is smaller than that one.
An example:
Position: 1 2 3 4 5 6 7 The array: 20 3 10 5 1 9 100 Answer: 0 0 2 2 0 2 1
Can this problem be done in O(n)?
| Rev. | Lang. | By | When | Δ | Comment | |
|---|---|---|---|---|---|---|
| en4 |
|
Tribbiani | 2017-07-12 16:22:43 | 47 | ||
| en3 |
|
Tribbiani | 2017-07-12 16:22:10 | 4 | ||
| en2 |
|
Tribbiani | 2017-07-12 16:15:09 | 39 | Tiny change: 'elements. We want ' -> 'elements. The elements is in the range $10^{9}$. We want ' | |
| en1 |
|
Tribbiani | 2017-07-12 16:10:21 | 418 | Initial revision (published) |
