abcd1204's blog

How to solve poblem uva-12776
By abcd1204, 10 years ago, In English

Here is the LINK Please give some hint and [pseudocode(if needed)]

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
//b[x] is maximum index y : a[x] % a[y] == 0, x <= i && y <= i, (x > y || y < x)

for (int i = 0; i < n; ++i) {
	lastPosOf[a[i]] = i;
	for (all d : a[i] % d == 0)
		b[i] = max(b[i], lastPosOf[d]);
	for (all j : a[j] % a[i] == 0)
		b[j] = max(b[j], i);

	for (all q in Queries where q.R == i) {
		sum = 0;
		// { this part can be done in O(Log(n)^2)
		// using segment tree
		for (int j = q.L; j <= q.R; j++)
			if (b[j] >= q.L)
				sum++;
		// }
		ans[q.Id] = sum;
	}
}
→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

there is an editorial by dragoon shanto vaiya here is the link

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I saw this tutorial ,i am kind of new what he says.So, it's become hard for me to implement it. If you give your source code, it would be very helpful for me. Thank u in advance.

    → Reply