To admins: Don't you think that it would be correct to increase Java-TL for this task to, e.g, 0.5 seconds (if it is possible)?
When I tried to submit this problem first time, I used prewritten RB-Tree code, using generics and classes for every node. This class is not so slow, a bit faster that java.util.TreeSet. When I'd got TL9, I rewrote it, using only primitive types and arrays. But it became TL10. That code, rewritten letter-by-letter in pure C, became AC in 0.031...
Сertainly, another(simplier?) data structure can lead to Java-AC, but probably it is incorrect to force Java-writers to use non-asymptotical optimizations (especially Java is the official language of ACM competition).

Edited by author 06.08.2007 23:34

Edited by author 06.08.2007 23:37

Edited by author 07.08.2007 00:01

Unfortunately, TL for this problem can't be increased. Bruteforce solution works very fast even with Java. You can try your sophisticated algorithms solving problem 1090. But this problem have to be solved using fastest algorithm in all senses

What do you use to read input?
maybe some optimizations in this direction can help

I think do not problem Java program.Problem I think  this he algortms.I working this 1028 solution at the Java but
came back TL time=0.296. You are use algortms quiksort or
binarysearch.

AC in Java 0.234sec using java.util.Scanner and fenwick's tree.

And AC in Java 0.125sec using java.io.StreamTokenizer instead of java.util.Scanner

Because of Timus processor upgrade this autumn. :-) And what time of the simplest O(n^2) solution now? :-) Maybe less than 0.25...

No, I use insertionsort and TL#9.