Unusual Runtime Error when performing Mo's Algorithm in C++
Разница между en1 и en2, 239 символ(ов) изменены
I ran into a runtime error when trying to solve [problem:1514D] with Mo's Algorithm. Part of the problem requires one to find the counts of an element within a range if it's greater than or equal to about half the counts of elements in the range. One way to solve it is to use Mo's Algorithm to keep track of the most common element in range and its counts.↵

I sort the queries in the standard way where the left boundaries are grouped together in blocks of about sqrt of the number of elements. Within a "left block", the right queries are sorted in increasing order if the "left block" is an even block, otherwise it is sorted in decreasing order (so that the right points zigzag left-right-left-right through alternating blocks).↵

I have found that using the following within the sort criterion gives a runtime error ([submission:235446182]):↵

~~~~~↵
if (block1 == block2) {↵
    // to ensure that the right portion sweeps in alternate directions between adjacent blocks↵
    if (block1% 2 == 0 && r < other.r) {↵
        return true;↵
    }↵
    if (block1 % 2 == 1 && r >= other.r) {↵
        return true;↵
    }↵
}↵
~~~~~↵

and the following does not ([submission:235448205]).↵

~~~~~↵
if (block1 == block2) {↵
    // to ensure that the right portion sweeps in alternate directions between adjacent blocks↵
    if (block1% 2 == 0 && r < other.r) {↵
        return true;↵
    }↵
    // if (block1 % 2 == 1 && r >= other.r) { // This gives run time error↵
    if (block1 % 2 == 1 && r > other.r) {↵
        return true;↵
    }↵
}↵
~~~~~↵

I also see that I am not the only person who faced this problem
 and fixed it with. Here are [user:nawa,2023-12-11]'s codes and his fix using a similar change: runtime error [submission:129082770] vs accepted [submission:129084946].↵

I
t will be help am not a native C++ user and I cannot figure out what went wrong. I will be grateful if someanyone can shed some light on what may cause this error. I think that it likely occurred during the sorting process, or during the handling of the querieshave caused this error.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский YMSeah 2023-12-11 05:37:03 9
en2 Английский YMSeah 2023-12-11 04:48:12 239 (published)
en1 Английский YMSeah 2023-12-11 04:41:17 1965 Initial revision (saved to drafts)