Submission #1216514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216514		lopkus	Garaža (COCI17_garaza)	C++20	0 / 160	4094 ms	1092 KiB

garaza

#include <bits/stdc++.h>

signed main() {
  int n, q;
  std::cin >> n >> q;
  std::vector<int> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::vector<int> f(n + 1, n + 1);
  for(int i = 1; i <= n; i++) {
    int gcd = 0;
    for(int j = i; j <= n; j++) {
      gcd = std::__gcd(gcd, a[j]);
      if(gcd == 1) {
        f[i] = j;
        break;
      }
    }
  }
  while(q--) {
    int type;
    std::cin >> type;
    if(type == 1) {
      int pos, x;
      std::cin >> pos >> x;
      a[pos] = x;
      for(int i = pos; i >= 1; i--) {
        if(f[i] < pos) {
          continue;
        }
        int gcd = 0;
        for(int j = i; j <= n; j++) {
          gcd = std::__gcd(gcd, a[j]);
          if(gcd == 1) {
            f[i] = j;
            break;
          }
        }
      }
    }
    else {
      int l, r;
      std::cin >> l >> r;
      int ans = 0;
      for(int i = l; i <= r; i++) {
        ans += std::min(f[i], r + 1) - i;
      }
      std::cout << ans << "\n";
    }
  }
}

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