Submission #48971

#	Time	Username	Problem	Language	Result	Execution time	Memory
48971		ami	Garaža (COCI17_garaza)	C++14	160 / 160	1121 ms	29900 KiB

garaza

#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using i64 = long long;
using vii = vector<pair<int,int>>;

struct node {
  i64 count=-1;
  vii p,s;

  void set(int x) {
    count=(x==1 ? 0 : 1);
    p=s={make_pair(x,1)};
  }
};

i64 merge_count(const vii &S, const vii &P) {
  i64 res=0,r=0,psum=0;
  per(l,0,sz(S)) {
    while (r<sz(P) && __gcd(S[l].first,P[r].first)>1) {
      psum+=P[r].second;
      r+=1;
    }
    res+=S[l].second*psum;
  }
  return res;
}

vii comb(vii a, const vii &b) {
  int cur=a.back().first;
  for (const auto &x:b) {
    cur=__gcd(cur,x.first);
    if (cur==a.back().first) {
      a.back().second+=x.second;
    } else {
      a.emplace_back(cur,x.second);
    }
  }
  return a;
}

node merge_nodes(const node &L, const node &R) {
  if (L.count==-1) return R;
  if (R.count==-1) return L;

  node res;
  res.count=L.count+R.count+merge_count(L.s,R.p);
  res.p=comb(L.p,R.p);
  res.s=comb(R.s,L.s);
  return res;
}

int const N=1<<17;
int n,q;
node tr[2*N];

void update(int i, int x) {
  tr[i+=N].set(x);
  for (i/=2; i>0; i/=2) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
}

i64 get(int l, int r) {
  node L,R;
  l+=N;
  r+=N;
  while (l<=r) {
    if (l%2==1) { L=merge_nodes(L,tr[l]); }
    if (r%2==0) { R=merge_nodes(tr[r],R); }
    l=(l+1)/2;
    r=(r-1)/2;
  }
  return merge_nodes(L,R).count;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout<<fixed<<setprecision(10);

  cin>>n>>q;
  rep(i,0,n) {
    int x;
    cin>>x;
    tr[i+N].set(x);
  }

  per(i,1,N) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }

  rep(iq,0,q) {
    int t,l,r;
    cin>>t>>l>>r;
    if (t==1) { update(l-1,r); } else { cout<<get(l-1,r-1)<<'\n'; }
  }

  return 0;
}

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