subbu988's blog

By subbu988, history, 6 weeks 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

»
6 weeks 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).

  • »
    »
    6 weeks 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?

    • »
      »
      »
      6 weeks 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

      • »
        »
        »
        »
        6 weeks 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?

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Just an error, difference in ~50ms can exist

          • »
            »
            »
            »
            »
            »
            6 weeks 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?

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I dont use SPOJ, so maybe its normal difference xD

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why do you mix in one code printf/scanf and cin >> l >> r;? Your fixed solution gives 0.79ms, if you change cin >> l >> r; on scanf( "%d %d", &l, &r);. And do you really need memset?