jugal_sahu's blog

By jugal_sahu, 9 years ago, In English

I was trying to solve D-query here problem on spoj.I searched for the solution and found one blog here and solution here.I got accepted.But the problem is that when i am sorting queries using qsort function it's giving tle.

when i am using this with sort function it's fine

bool cmp(node x, node y) { if(x.x/BLOCK != y.x/BLOCK) { return x.x/BLOCK < y.x/BLOCK; } return x.y < y.y; }

but when i am using this with qsort it's giving tle

int inline cmp(const void *xx,const void *yy) { nod *x = (nod *) xx; nod *y = (nod *) yy; if(x->x!=y->x) return (x->x>y->x)?1:-1; return (x->y>y->y)?1:(x->yy)?-1:0; }

my code is here

Please any one give me answer why is this happening....thanks in advance

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The BLOCK thing stands there for a reason. You cannot just sort queries as pairs and get complexity. Read the blog post (which you linked) more carefully.