12003 - Array Transformer

[sith]

Hi
I solved this problem with O(n). but got TLE

Is there any faster algorithm. Do we need some faster structure, some thing like tree or Cartesian tree? Am I w

[brianfry713]

It takes O(n+m) just to read the input so your program can't run correctly as fast as O(n).

Try splitting the array into sqrt(n) blocks.

[Repon kumar Roy]

get AC
wrong in binary search
1.Use sqrt-decomposition
2.Sort the every box/bucket

testcase :

Code: Select all

9 10 42
30 35 41 18 17 13 1 41 21 
3 9 28 8
6 8 15 8
1 4 31 1
1 6 35 5
6 7 30 9
1 3 31 3
5 7 8 9
4 8 40 3
3 4 3 7
4 8 23 3

Output :

Code: Select all

21
35 
25 
18 
28 
13 
0 
28 
14