oj.uz

Submission #49217

# Submission time Handle Problem Language Result Execution time Memory
49217 2018-05-23T23:21:25 Z ami Garaža (COCI17_garaza) C++14
160 / 160
 1495 ms 25632 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<typename T, typename Op>
struct segment_tree {
  int n;
  Op op;
  T identity;
  vector<T> f;
  explicit segment_tree(int n_, Op op_=Op(), T identity_=T())
    :n(n_), op(op_), identity(identity_), f(2*n, identity) {}
  T& operator[](int i) {
    return f[i+n];
  }
  void build() {
    per(i,1,n) { f[i]=op(f[2*i],f[2*i+1]); }
  }
  void update(int i) {
    i+=n;
    for (i/=2; i>0; i/=2) { f[i]=op(f[2*i],f[2*i+1]); }
  }
  void update(int i, const T &x) {
    f[i+n]=x;
    update(i);
  }
  T query(int l, int r) {
    T L=identity;
    T R=identity;
    l+=n;
    r+=n;
    while (l<=r) {
      if (l%2==1) { L=op(L,f[l]); }
      if (r%2==0) { R=op(f[r],R); }
      l=(l+1)/2;
      r=(r-1)/2;
    }
    return op(L,R);
  }
};

template<typename T, typename Op>
segment_tree<T, Op> make_segment_tree(int n, Op op, T identity) {
  return segment_tree<T, Op>(n, op, identity);
}

struct node {
    i64 count;
    vii p,s;

    node():count(-1) {}
    node(i64 cc, vii pp, vii ss):count(cc),p(pp),s(ss) {}

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

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

    cin>>n>>q;
    auto st = make_segment_tree(n,merge_nodes,node());
    rep(i,0,n) {
    int x;
    cin>>x;
    st[i].set(x);
    }

    st.build();

    rep(iq,0,q) {
    int t,l,r;
    cin>>t>>l>>r;
    if (t==1) {
        st[l-1].set(r);
        st.update(l-1);
    } 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 8 ms 632 KB Output is correct
2 Correct 21 ms 1128 KB Output is correct
3 Correct 43 ms 1580 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 5600 KB Output is correct
2 Correct 287 ms 8056 KB Output is correct
3 Correct 318 ms 8056 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 12888 KB Output is correct
2 Correct 680 ms 13060 KB Output is correct
3 Correct 915 ms 14980 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1482 ms 25424 KB Output is correct
2 Correct 1481 ms 25632 KB Output is correct
3 Correct 1495 ms 25632 KB Output is correct