oj.uz

Submission #48974

# Submission time Handle Problem Language Result Execution time Memory
48974 2018-05-21T01:45:15 Z ami Garaža (COCI17_garaza) C++14
160 / 160
 1504 ms 26904 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>>;

template<int N, typename Node>
struct segment_tree {
  Node tr[2*N];

  void set(int i, const Node &x) {
    tr[i+N]=x;
  }
  void build() {
    per(i,1,N) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
  }
  void update(int i, const Node &x) {
    tr[i+=N]=x;
    for (i/=2; i>0; i/=2) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
  }
  Node query(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);
  }
};

struct node {
  i64 count;
  vii p,s;

  node():count(-1) {}
  node(i64 cc, vii pp, vii ss):count(cc),p(pp),s(ss) {}
  node(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 merge_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;

  i64 count=L.count+R.count+merge_count(L.s,R.p);
  auto p=merge_comb(L.p,R.p);
  auto s=merge_comb(R.s,L.s);

  return {count,p,s};
}

int const MAXN=110000;
int n,q;
segment_tree<MAXN,node> st;

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;
    st.set(i,node(x));
  }

  st.build();

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

  return 0;
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12536 KB Output is correct
2 Correct 35 ms 12900 KB Output is correct
3 Correct 53 ms 13360 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 15384 KB Output is correct
2 Correct 372 ms 16836 KB Output is correct
3 Correct 344 ms 16836 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 19692 KB Output is correct
2 Correct 716 ms 19856 KB Output is correct
3 Correct 768 ms 20716 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1196 ms 26808 KB Output is correct
2 Correct 1467 ms 26904 KB Output is correct
3 Correct 1504 ms 26904 KB Output is correct