for i=1~N

  for j=1~i

까지 돌았기때문에, 1~N까지의합, 즉 거의 N^2/2의 시간이 걸리죠. 그러므로 시간안에 나오는게 맞습니다.

또한, 궁금하시다면 다른 분들 소스를 참고해보세요. 제가 본 바로는, NlogN으로 푸신분은 일단 못찾았습니다.

1만이면 어지간해선 n^2 빠르게 나옵니다. 완전 느리게 짠게 아니면.. 그리고 로컬은 보통 느려요.

n^2보다 빠른 풀이가 옛날에 궁금해서 코포 분들에게 물어본게 있는데.. http://codeforces.com/blog/entry/43729

crazy111님

일단 다른분들 소스는 봤구요.

뭐.. 저도 약간의 오버헤드는 있지만, 거의 비슷하게 풀었습니다.

쿠사가님 코드포쓰 링크 감사합니다

제가 100% 이해하려면 시간이 걸리겠지만,

어쨋든 Full N^2이 아니고, overap 된 부분은 건너뛰고 loop를 타기때문에, naive한 N^2에 비해 속도가 빠르다는거 같구요.

세그먼트트리를 활용해서 가능할것 같다는 아이디어도 보이는것 같네요.