oj.uz

Submission #48972

# Submission time Handle Problem Language Result Execution time Memory
48972 2018-05-20T23:15:36 Z ami Garaža (COCI17_garaza) C++14
160 / 160
 1107 ms 27732 KB 
#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 MAXN=110000;
int n,q;
node tr[2*MAXN];

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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12536 KB Output is correct
2 Correct 27 ms 13032 KB Output is correct
3 Correct 42 ms 13216 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 15484 KB Output is correct
2 Correct 251 ms 16992 KB Output is correct
3 Correct 266 ms 16992 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 19992 KB Output is correct
2 Correct 617 ms 20256 KB Output is correct
3 Correct 608 ms 20672 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 930 ms 27732 KB Output is correct
2 Correct 1083 ms 27732 KB Output is correct
3 Correct 1107 ms 27732 KB Output is correct