subbu988's blog

By subbu988, history, 3 years ago, In English

I am trying to solve a SegTree Problem, I've written an O(N,lgN) segment tree solution using segment tree. With the given constraints I see that this approach passes For example the solution here passes the problem. I've seen that the verdict of this problem differed from TLE to AC considering memset() for each test case, usage of printf, scanf vs cin/cout and \n instead of endl. I couldn't differentiate between these two solutions and the reason the latter passes and the former results in TLE. Can someone help with this?

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Look at this. Near a TL(3.96), I think its just a bad problem(with so many queries).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the reply, Did you passed the problem with the changes in the link in 3.96? (Are you buyolitsez?). I made the changes you made and still is a TLE and I don't see difference in the tweak?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I get AC, also u can try to write your ST from down to up(without recursion)

      https://codeforces.com/blog/entry/18051

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks @king_of_tt. I submitted the tweak and got an TLE. I resubmitted it again and it got AC. So it's just a bad problem whose verdict even depends upon the judge load factor?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Just an error, difference in ~50ms can exist

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, that is negligible. I've submitted the same solution 5-6 times. Once it got AC with >4.5S. So its not ~50ms right?

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I dont use SPOJ, so maybe its normal difference xD