oj.uz

Submission #165637

# Submission time Handle Problem Language Result Execution time Memory
165637 2019-11-27T22:33:46 Z Milki Garaža (COCI17_garaza) C++14
0 / 160
 2920 ms 34052 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl
#define int long long

typedef long long ll;
typedef pair<int, int> point;

const int mod = 1e9 + 7;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

const int off = 1 << 17;

struct Node{
  vector <point> prefix = {}, suffix = {};
  ll sum = 0;

  Node(){}
  Node(int val){
    prefix.clear(); suffix.clear();
    prefix.pb(point(val, 1));
    suffix.pb(point(val, 1));
    if(val > 1)
      sum = 1;
    else
      sum = 0;
  }
};

Node merge( Node A, Node B ){
  if(sz(A.prefix) && A.prefix[0].first == 0) return B;
  if(sz(B.prefix) && B.prefix[0].first == 0) return A;

  Node ret = Node();
  ret.prefix = A.prefix;
  ret.suffix = B.suffix;
  int curr;

  if(sz(A.prefix)){
    curr = A.prefix.back().first;
    REP(i, sz(B.prefix)){
      int tmp = __gcd(curr, B.prefix[i].first);
      if(curr == tmp)
        ret.prefix.back().second += B.prefix[i].second;
      else
        ret.prefix.pb(point(tmp, B.prefix[i].second));

      curr = tmp;
    }
  }
  else ret.prefix = B.prefix;
  if(sz(B.suffix)){
    curr = B.suffix.back().first;
    REP(i, sz(A.suffix)){
      int tmp = __gcd(curr, A.suffix[i].first);
      if(curr == tmp)
        ret.suffix.back().second += A.suffix[i].second;
      else
        ret.suffix.pb(point(tmp, A.suffix[i].second));

      curr = tmp;
    }
  }
  else ret.suffix = A.suffix;

  ret.sum += A.sum + B.sum;
  int rt = -1;
  ll rt_sum = 0;

  REP(i, sz(A.suffix)){
    while(rt + 1 < sz(B.prefix) && __gcd(B.prefix[rt + 1].first, A.suffix[i].first) > 1){
      rt_sum += B.prefix[rt + 1].second;
      rt ++;
    }
    if(rt != -1 && __gcd(B.prefix[rt].first, A.suffix[i].first) > 1)
      ret.sum += (ll)A.suffix[i].second * rt_sum;
  }

  return ret;
}

struct Tournament{
  Node t[2 * off];

  void update(int x, int val){
    x += off;
    t[x] = Node(val);
    for(x >>= 1; x > 0; x >>= 1)
      t[x] = merge(t[x * 2], t[x * 2 + 1]);
  }
  Node get(int x, int lo, int hi, int a, int b){
    if(lo >= b || hi <= a) return Node(0);
    if(lo >= a && hi <= b) return t[x];
    int mid = (lo + hi) >> 1;
    return merge(get(x * 2, lo, mid, a, b),
                 get(x * 2 + 1, mid, hi, a, b));
  }
} T;

int n, q;

signed main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n >> q;
  REP(i, n){
    int x; cin >> x;
    T.update(i, x);
  }
  REP(i, q){
    int tip; cin >> tip;
    if(tip == 1){
      int x, v; cin >> x >> v;
      x --;
      T.update(x, v);
    }
    else{
      int l, r; cin >> l >> r;
      l --; r --;
      cout << T.get(1, 0, off, l, r + 1).sum << "\n";
    }
  }
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 14844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 518 ms 18700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1501 ms 24108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2797 ms 33864 KB Output is correct
2 Incorrect 2920 ms 34052 KB Output isn't correct
3 Halted 0 ms 0 KB -