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

Help for problem Pair of numbers 290 div2 D

Автор fullbuster, история, 8 лет назад, По-английски

Problem link http://mirror.codeforces.com/problemset/problem/359/D

Here is my solution for the problem http://mirror.codeforces.com/contest/359/submission/27581236 I first created lefty[i] and righty[i] which contains the left and right index of the farthest number such that all numbers between farthest number and number at index i are divisible by a[i] . I created it using sparse table . My solution is failing at testcase 25 can someone please help me to debug it.

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

27584809 Be careful about constraints next time :)

(log(n) is equal to 18, hence your sparse table fails).

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится 
    ///////////sparse table gcd(l,r)////////////
	for(int i=0;i<n;i++)g[i][0]=a[i];
	for(int j=1;j<20;j++){
		for(int i=0;i+(1<<j)-1<n;i++){
			g[i][j]=gcd(g[i][j-1],g[i+(1<<(j-1))][j-1]);
		}
	}

    When j=19 i=0 we have 0+(1<<19)-1 = 524287 > n so how will this change make any difference.

    Please correct me for what i am missing.

    → Ответить