jaiyant_jakhar's blog

getting tle for problem 380C
By jaiyant_jakhar, history, 3 years ago, In English

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

  • Vote: I like it
  • +5
  • Vote: I do not like it

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

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

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

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));
→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply