OJ Board

can a O(n*n*lgn) solution be ACed?

this problem occurs so frequently!

i think it's a bad description.

@chengouxuan

I tried it with segment tree but got TLE. I don't know how to do the inversion fast.

Can you explain how you solved it with sqrt(n) X sqrt(n) table??


this is my algorithm's outline.

there are O(sqrt(n)) rows. at each query, you shouldn't process all elements in all rows that are ...

can any one explain how to solve it using segmen tree in more details? i solve it by compress all pirates into a table of sqrt(n) X sqrt(n) with time O(sqrt(n)) and my algorithm runs 3.8 seconds.

i'm really interested in knowing the correct approach to this problem, so can anyone please reply to this thread

i tried different approaches, but they all failed. now i got AC but in 2.7 seconds :-? (so clearly my algo. isn't good and there are much better ones)

the idea of my soln is that i ...

I got ACed by converting every lower case letter into upper case letter in my own string comparing function.

is it a connected graph?

how to solve it using dijkstra's algorithm?

in

3 3
2 3 4
4 5
1 1 1 1 1
0 0


out

2 6
1 4