MagicSpark's blog

By MagicSpark, history, 2 months ago, In English,

When I am solving 1197D,I didn't see m<=10 and then I find a solution that can solve m<=n<=3e5

Here is my solution:

The range [l,r] is equal to [l,l+m-1],[l+m,l+2m-1]....[l+xm,r]

then we will enumeration the value of l+xm.

We consider every reminder(from 0 to m-1) of position module m and solve them independently.

When we are solving each of the reminders,we have v[i]-->the value of the ith range(from the ith position fits the reminder to the next),then we will consider the value of two parts

First:[l,l+m-1],[l+m,l+2m-1].....[l+(x-1)m,l+xm-1]

Second:[l+xm,r]

We can use segment tree to get the max prefix sum of [l+mx,l+(m+1)x-1],then it's the second part.

When we are solveing the first part,we need to find the min value of the prefix sum of v[i].

This can also be done using segment tree.

Then the answer for each l+xm is First+Second-k.

Here is my submission https://codeforces.com/contest/1197/submission/57841454

The final answer is the maximum of them.

Overall complexy O(n log n) with big constants

I wanna know if there are better solutions.

If you have,please share under this blog.

Read more »

 
 
 
 
  • Vote: I like it
  • +24
  • Vote: I do not like it

By MagicSpark, history, 6 months ago, In English,

I tried to solve 1153F. I got up with an unusual idea.Then this is my code.I clone the 1153F to a mashup.And I accepted with maximum time 1825 ms.But the time limit is only 1 second. Can some one help me to optimize the code? (Because it is not so slow,I think I don't need to change the algorithm,And I only get this way to solve the problem) [submission:53500731] in the mashup and 53500951 in the contest.

Read more »

 
 
 
 
  • Vote: I like it
  • -34
  • Vote: I do not like it

By MagicSpark, history, 8 months ago, In English,

When will the of educational round 60 be published?Usually there is only a few hours after the contest the tutorial will be published.But now, almost two days past,where is the tutorial? (Sorry for my pool English and poor rating.) Oh sorry it published.

Read more »

 
 
 
 
  • Vote: I like it
  • +14
  • Vote: I do not like it