Блог пользователя abcd1204

How to solve poblem uva-12776
Автор abcd1204, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится 
//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;
	}
}
→ Ответить
»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить