What's the expected complexity of Codeforces 827A/828C ?

Revision en2, by Marco_L_T, 2017-07-12 19:35:41

I noticed that there existed a method to solve Codeforces 827A/828C like this:Submission

It ran really fast that it became one of the quickest solutions to this problem.However,when I opened the code,I found it was just a naive implemention only with some optimizations.

But if I gave the following data:


all the 1000 queries have the same string with length 1000 and k=1000,

the following numbers are 1,1001,....,999001,1000000,

the sum of all ki is 10^6 and the sum of string length is 10^6,which satisfies the data range.

In this condition,the code will have up to 10^9 times of calculation and I don't think it can pass within 2 seconds.

So can anyone please if it's the expected solution to the problem? Thanks!


  Rev. Lang. By When Δ Comment
en2 English Marco_L_T 2017-07-12 19:35:41 3 Tiny change: 'the follow numbers a' -> 'the following numbers a'
en1 English Marco_L_T 2017-07-12 19:35:12 861 Initial revision (published)