Блог пользователя VandanRogheliya

Автор VandanRogheliya, история, 4 года назад, По-английски

I was solving D-Query question from SPOJ.

This was my original solution using an offline approach. Strangely for queries, more than 16 this program gave a segmentation fault

I modified the program according to one editorial to this and got AC

Note: Both programs only differ in sorting comp_ends function:

In 1st approach

int comp_ends(const Info& a, const Info& b) {
  if (a.type == b.type) {
    if (a.type == Q) return a.r <= b.r;
    return a.i <= b.i;
  } else {
    if (a.type == Q) return a.r < b.i;
    return a.i <= b.r;
  }
}

In 2nd approach

int comp_ends(const Info& a, const Info& b) {
  if (a.end < b.end) return true;
  else if (a.end == b.end) return a.type == I;
  else return false;
}

It will be very helpful if someone pointed out my mistake.

Thanks!

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

The comparison must return val1<val2, not val1<=val2, because the callers expect that it works that way.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    but why was it working for a vector of length <= 16 and giving error for length > 16 ?

    P.S: thank you for helping out!