Damon's blog

Problem 155 — Cartesian Tree ! Time Limit

By Damon, 11 years ago, In English

Hi !

I am trying to answer problem 155 at ACM.SGU.RU site .

Cartesian Tree

My algortihm is sort by a[i] elements , then create a BST by k[i] elements.

I know my algorithm in worse case is O(n^2) and n can be 50000 ! So my answer get TLE .

What can I do for this problem ? Is my algorithm wrong or can be optimize ?

Here is My Code

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Cartesian tree is a well-known data structure, that can be created in O(N). You can read about it here.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Just to note, O(N) cartesian-tree building algorithm requires points to be sorted by x-coordinate beforehand. If that's not the case, this task is clearly no easier than general sorting problem, so the best time we can achieve is O(N log N).

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i accept this problem via segment tree(its so hard to code for me) but one of my friend have a very very creative solution and i think his solution is near to your solution but you must change your approach to optimize your algorithm! sorry for my bad english!

→ Reply