Muito interessante.
Só o $O(\sqrt{k} \cdot \lg{n})$ funcionou aí? Achei que deveria funcionar mas acabei de tomar TLE assim.
Muito estranho. O tempo de execução no meu computador é muito baixo:
tiago@alice ~/icpc/pku $ g++ -v
Target: x86_64-pc-linux-gnu
gcc version 4.3.3 (Gentoo 4.3.3-r2 p1.1, pie-10.1.5)
tiago@alice ~/icpc/pku $ g++ -o 2800 2800.cpp -O2
tiago@alice ~/icpc/pku $ time ./2800 < 2800.i1 # 5 3
7
real 0m0.002s
user 0m0.000s
sys 0m0.003s
tiago@alice ~/icpc/pku $ time ./2800 < 2800.i2 # 11 11
22
real 0m0.002s
user 0m0.001s
sys 0m0.001s
tiago@alice ~/icpc/pku $ time ./2800 < 2800.i3 # 1000000000 500000000
294383241290555707
real 0m0.029s
user 0m0.028s
sys 0m0.001s
tiago@alice ~/icpc/pku $ time ./2800 < 2800.i4 # 1000000000 1000000000
177532965887639372
real 0m0.042s
user 0m0.039s
sys 0m0.003s
Ninguém tá tendo problema de TLE nesse problema além de mim?
Tiago, tenta submeter em G++ em vez de C++. Embora o C++ seja mais "confiável", ele é mais lento, acho … Eu submeti meu código $O(\sqrt{k} \cdot \lg{n})$ e teve uma diferença de ~100ms para C++ (pode sido apenas o tráfego no servidor também, não sei). Mais uma coisa lenta são as operações com inteiros de 64 bits, então é bom usá-los apenas quando necessário. Outra coisa, sua busca binária está recursiva? O meu código está recursivo, e passa, mas derrepente isso pode melhorar o tempo!
Funcionou com G++! Esse PKU é muito estranho.
Obrigado!
Nossa, comigo foi exatamente o contrário!
Fiz a solução $\mathcal O (\sqrt k)$ e tomei TLE quando submeti com o G++ por engano. Resubmeti a mesma com C++ e passou em 200MS.