제출 #1026021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026021		vjudge1	Garaža (COCI17_garaza)	C++17	0 / 160	4070 ms	2644 KiB

garaza

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int M = 2 << 17, N = 1e5+5;
int gc[M], a[N], n, q;

void update(int p, int val, int s = 0, int e = n, int v = 1)
{
  if(p < s || e <= p) return;

  if(e - s == 1)
    {
      gc[v] = val;
      return;
    }
  
  int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
  update(p, val, s, mid, lc);
  update(p, val, mid, e, rc);
  gc[v] = gcd(gc[lc], gc[rc]);
}

int GCD(int l, int r, int s = 0, int e = n, int v = 1)
{
  if(r <= s || e  <= l) return 0;
  if(l <= s && e <= r) return gc[v];
  int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
  return gcd(GCD(l, r, s, mid, lc), GCD(l, r, mid, e, rc));
}

int main()
{
  int q;
  cin >> n >> q;
  for(int i = 0; i < n; i ++)
    {
      cin >> a[i];
      update(i, a[i]);
    }
  while(q--)
    {
      int t, x, y;
      cin >>t >> x >> y;
      x--;
      if(t == 1)
	{
	  a[x] = y;
	  update(x, a[x]);
	}
      else
	{
	  ll fans = 0;;
	  for(int i = x; i < y; i ++)
	    {
	      int ans = 0;
	      for(int j = 20; j >= 0; j--)
		{
		  ans += (1 << j);
		  if(i + ans > y || GCD(i, i + ans) == 1)
		    ans -= (1 << j);
		}
	      fans += ans;
	    }
	  cout << fans << endl;
	}
    }
  return 0;
}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 40
• Subtask 4: 0 / 40