of course you need O(n) and I had it but
I was mad about this(TLE), but I thought a little and tried to use
char s[200010]
and now
AC 0.031))))))))))))))
don't use list or string in this problem
write your own implementation of std::list
good luck)

Edited by author 10.07.2009 23:29

Edited by author 10.07.2009 23:49

i use vectors and got AC in 0.046s 557 КБ with 5 lines of code))

std::list<char> simply gives AC in 0.343 sec.