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

getting tle for problem 380C
Автор jaiyant_jakhar, история, 3 года назад, По-английски

also i am using pass by reference and segment tree method. not able to optimize any further, i think my time complexity is O(nlogn) only, but getting tle, not able to find mistake, please help solution 194602929 solution link : https://mirror.codeforces.com/contest/380/submission/194602929

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

»
3 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Maybe you should just change to a different data structure, e.g., a sparse table. The constant factor for SegmentTrees are too big.

→ Ответить
»
3 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Maybe the code is close to avoid TLE so you can try a few minor optimizations. For examples:

A. Change

    full = min(seg_tree[2 * ind + 1][0], seg_tree[2 * ind + 2][1]);
    seg_tree[ind][2] += full + seg_tree[2 * ind + 1][2] + seg_tree[2 * ind + 2][2];
    seg_tree[ind][0] = seg_tree[2 * ind + 1][0] + seg_tree[2 * ind + 2][0] - full;
    seg_tree[ind][1] = seg_tree[2 * ind + 1][1] + seg_tree[2 * ind + 2][1] - full;

    to be:
    int[] s1 = seg_tree[2 * ind + 1];
    int[] s2 = seg_tree[2 * ind + 1];
    int[] s = seg_tree[ind];
    full = min(s1[0], s2[1]);
    s[2] += full + s1[2] + s2[2];
    s[0] = s1[0] + s2[0] - full;
    s[1] = s1[1] + s2[1] - full;

B. Simplify query() to return int instead of vector.

C. Use int[4*n][3] instead of:

    vector<vector<int>> seg_tree(4 * n, vector<int>(3, 0));
→ Ответить
»
3 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

It's IO bottleneck, you can find some codeforces blogs on this topic.

Add ios_base::sync_with_stdio(false); at the start of your program. And don't use endl if flushing the buffer (needed in interactive problems only) is not needed as its slow; use '\n'.

Here is your submission with changes: https://mirror.codeforces.com/contest/380/submission/194658328

→ Ответить