How to solve the problem below in O(log2n) C++: You have the i'th element of an unsorted array. you have to find the nearest(absolute difference of the values is as small as possible) element of the i'th element from the right side.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/22/2024 20:20:56 (l3).
Desktop version, switch to mobile version.
Supported by
Impossible. You will spend at least O(n) to read everything and while you're reading you can just calc the answer.
If you're trying to solve for O(logn) per query. You can do binary search on set/sorted array etc.
maintain a set, iterate from n to 1. for each i, find the value closest to a[i] on set (can be done using lower_bound), then insert a[i] into set