Abinash's blog

Why difference of time is near 1 sec ?
By Abinash, 10 years ago, In English

I submit 2 solution of this problem , both are almost same . But this one need 2.31 sec and that one need 1.49 sec , why ?

If I change the second solution the compare function as

bool cp( Q a, Q b ) {
	int ax=a.L/tmt,bx=b.L/tmt;
	if ( ax!=bx ) return ax<bx;
	return (ax&1)?a.R<b.R:a.R>b.R;
}

and change the value of as 

tmt=(int)(1.514*sqrt(m)+1);

then it need .96sec to pass , why ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The struct query is different for both of them . In one you have declared l and r as long long while in the other one(the faster one) they are declared as int.

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

    And what about the compare function and value of tmt?

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

Try to submit the program taking your array a as int. Using long long making the computation slow. 9738918.

No need to declare struct element as long long and also no need to take input as 64 bit if the input can be fit into 32 bit. 9738898

→ Reply