That's true

Can you please elaborate more

I read this article, and checked your solution, but I am confused, especially about this part:

for(i=0;i<=n;i++)
{
    b[i]=b[i]*b[i];
}
gcd_convolution_inv(b);

Aren't we supposed to get the 'dp' array (the same one as in the official solution) after the first convolution? Why square it? Why inverse?

It's a wonderful solution and it's better than the Editorial!

and their multiples

damn, how did i not see that D:

Hi could you tell how to do that in O(n) for problem B. I got the idea like we need to move the ones from the last to zeros just before, but unable to implement it.

I have seen one implementation (below) in which we only need to consider the movements of zeros, but not sure what are takeaways from this.

void solve(){
	int n; cin>>n; 
	string s; cin>>s; 
	int start = n-1, end = n-1; 
	ll ans = 0;  
	for(; end >= 0; end--){
		while(start >= 0 && s[start] != '0') start--; 

		if(start < 0) {
			cout<<"-1 "; 
			continue; 
		}

		ans += end-start; 
		start--; 
		cout<<ans<<" "; 
	}

	cout<<endl; 
}
 

Thanks!

Your text to link here... I'd like to know why my code always times out, obviously I've restricted it to be able to output -1 directly as soon as the second pointer reaches n. Why on earth is this causing a timeout! Can you help me to solve the error of my answer?

I missed it too. I don't understand how in the solution, they say that the minimum will either occur at position 1 or position m. What if we have: (1, 1) (1, 2) (m-1, m) (m,m). Then the minimum will be any value between 2 and m-1, and the maximum will be either 1 or m, both possessing value 2.(Assuming m > 3 for simplicity of the example).

I also don't quite see how that is necessary for their algorithm to work? The whole line sweep thing doesn't seem to require that fact either, right? It just requires the minimum to be outside of all the current open segments?

I did the same ... cant figure out where it goes wrong ... did you find the error? UPD: nvm found the bug

why use trees tho

we are only selecting segments that contain x

sort the relevant segments by the left point and by the right point, you'll see.

Imagine the selected segments. The maximum is reached somewhere, let's say at X.

Now, there are two types of segments:

• Containing X: they are guaranteed to increase maximum (value at X) by 1, but may (or may not) also increase minimum by 1. So they are either good or neutral. Let's simply include them

• Not containing X: they are guaranteed not to change maximum (value at X), but may increase minimum. So they are either bad or neutral. Let's simply NOT include them

So, we include all segments containing X (and only them). Now let's say X=6 (and all segments contain X). You can't have minimum at, say 3, because that would require that vs[2] > vs[3], so there is some segment, that contains 2, but not 3 — but that is impossible because all segments contain X (so segment containing 2 and X would also contain everything in-between including 3).

Then we "brute force" all possible X's fast with Events:

https://mirror.codeforces.com/blog/entry/121618?#comment-1080014

Anyone? Why am I undercounting the number of non intersting pairs by above approach of op?

For a number x in a(consider distinct as I've precalculated their frequency)

cnew = #of multiples of x visited for the first time

cprev=#of multiples of x which were already visited by some y<x

Then new non intersting pairs introduced by x = cnew*(cnew-1)/2 + cprev*cnew

hey check this test case

1

15

2 2 2 2 2 2 2 2 2 2 2 3 5 10 15

ans=35

our output=36

Here we are not excluding the (10,15) pair as when iterating at 5 both 10 and 15 are already visited

Think of the harmonic lemma, i.e. $$$\sum_{i=1}^n{n/i} = O(n \ln n)$$$. Find out how that relates to the bound on the values of $$$a_i$$$.

It means that for each segment [l, r] we generate two "events":

• { l, "start" }

• { r, "end" }

Then we sort them by location and process them (events, not original segments) left to right:

• "start" event: increase current segment count, also check if new best score is achieved

• "end" event: decrease current segment count

Take a look at my solution, it should be quite readable

Take a look at Ticket 17117 from CF Stress for a counter example.

https://mirror.codeforces.com/blog/entry/121618?#comment-1080014

You compute prefix/suffix sum. Something like this:

vector<int> prefix1(n+1);
for (int i = 0; i < n; i++)
    prefix1[i+1] = prefix1[i] + (s[i] == '1');
// ... later
prefix1[b] - prefix[a] // number of 1s between 'a' and 'b' (not inclusive 'b')

vector<int> suffix0(n+1);
for (int i = n-1; i >= 0; i--)
    suffix0[i] = suffix0[i+1] + (s[i] == '0');
// ... later
suffix0[a] - suffix0[b] // number of 0s between 'a' and 'b' (not inclusive 'b')

You don't need to compute prefix/suffix sum in this case (I didn't — note that I moved the opposite direction though — right to left), but it might be easier to solve with them sometimes