Submission #1025984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025984		vjudge1	Garaža (COCI17_garaza)	C++17	0 / 160	1212 ms	8788 KiB

garaza

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int M = (2 << 17), N = 1e5+5, K = 29;
int n, q, a[N];

struct node {
  ll lazy, sm;
} seg[M];

void push(int v, int s, int e)
{
  int lc = 2 * v, rc = lc + 1, mid = (s + e) / 2;
  seg[lc].lazy = seg[rc].lazy = seg[v].lazy;
  seg[v].lazy = 0;
  seg[lc].sm = seg[lc].lazy * (mid - s);
  seg[rc].sm = seg[rc].lazy * (e - mid);
}

void SetRange(int l, int r, int val, int s = 0, int e = n, int v = 1)
{
  if(r <= s || e <= l) return;

  if(l <= s && e <= r)
    {
      seg[v].lazy = val;
      seg[v].sm = seg[v].lazy * (e - s);
      return;
    }
  
  if(seg[v].lazy)
    push(v, s, e);
  
  int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
  SetRange(l, r, val, s, mid, lc);
  SetRange(l, r, val, mid, e, rc);
  
  seg[v].sm = seg[lc].sm +  seg[rc].sm;
}

ll get(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 seg[v].sm;
  if(seg[v].lazy)
    push(v, s, e);
  int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
  return get(l, r, s, mid, lc) + get(l, r, mid, e, rc);
}

int gc[M];

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));
}

ll sm(int x, int y)
{
  return (1ll * y * (y - 1)) / 2 - (1ll * x * (x - 1)) / 2;
}

int main()
{
  cin >> n >> q;
  for(int i = 0; i < n; i ++) {
    cin >> a[i];
    update(i, a[i]);
  }
  
  for(int i = 0; i < n; i ++)
    {
      int ans = 0;
      for(int j = 20; j >= 0; j--)
	{
	  ans += (1 << j);
	  if(i + ans > n || GCD(i, i + ans) == 1) ans -= (1 << j); 
	}
      SetRange(i, i + 1, i + ans);
    }

  while(q--)
    {
      int t, x, y;
      cin >> t >> x >> y;
      x--;
      if(t == 2)
	cout << get(x, y) - sm(x, y) << '\n';
      else
	{
	  a[x] = y;
	  update(x, a[x]);
	  vector<int> vec;
	  vector<int> val; 

	  vec.push_back(x);
	  int g = a[x], pos = x;
	  while(true)
	    {
	      for(int i = 20; i >= 0; i --)
		{
		  int l = pos - (1 << i) + 1;
		  if(l < 0) continue;
		  if(GCD(l, x + 1) == g) pos = l;
		}
	      pos--;
	      if(pos >= 0)
		{
		  vec.push_back(pos);
		  g = GCD(pos, x + 1);
		}
	      else
		break;
	    }
	  
	  reverse(vec.begin(), vec.end());
	  
	  for(int i : vec)
	    {
	      int ans = 0;
	      for(int j = 20; j >= 0; j--)
		{
		  ans += (1 << j);
		  if(i + ans > n || GCD(i, i + ans) == 1) ans -= (1 << j);
		}
	      val.push_back(i + ans);
	    }

	  SetRange(0, vec[0] + 1, val[0]);
	  for(int i = 1; i < vec.size(); i ++)
	    SetRange(vec[i - 1] + 1, vec[i] + 1, val[i]);
	}
    }
  
  return 0;
}

Compilation message (stderr)

garaza.cpp: In function 'int main()':
garaza.cpp:152:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |    for(int i = 1; i < vec.size(); i ++)
      |                   ~~^~~~~~~~~~~~

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