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
12003 - Array Transformer
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12003 - Array Transformer -TLE
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.
Try splitting the array into sqrt(n) blocks.
Check input and AC output for thousands of problems on uDebug!
-
- Learning poster
- Posts: 96
- Joined: Tue Apr 23, 2013 12:54 pm
Re: 12003 - Array Transformer
get AC
wrong in binary search
1.Use sqrt-decomposition
2.Sort the every box/bucket
testcase :
Output :
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
Code: Select all
21
35
25
18
28
13
0
28
14