oj.uz

Submission #165800

# Submission time Handle Problem Language Result Execution time Memory
165800 2019-11-28T23:41:37 Z Milki Garaža (COCI17_garaza) C++14
160 / 160
 2491 ms 30604 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

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(A.prefix.empty()) return B;
  if(B.prefix.empty()) return A;
  //assert(!A.prefix.empty() || !B.prefix.empty());

  Node ret = Node();
  ret.prefix = A.prefix;
  ret.suffix = B.suffix;
  ret.sum = A.sum + B.sum;

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

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

  int rt = -1;
  ll rt_sum = 0;

  for(int i = sz(A.suffix) - 1; i >= 0; --i){
    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];

  Tournament(){ REP(i, 2 * off) t[i] = Node(); }

  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(1);
    if(lo >= a && hi <= b) return t[x];
    int mid = (lo + hi) >> 1;
    Node lt = get(x * 2, lo, mid, a, b);
    Node rt = get(x * 2 + 1, mid, hi, a, b);
    //TRACE(lt.sum); TRACE(rt.sum);
    return merge(lt, rt);
    return merge(get(x * 2, lo, mid, a, b),
                 get(x * 2 + 1, mid, hi, a, b));
  }
} T;

int n, q;

int 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;
      T.update(x - 1, v);
    }
    else{
      int l, r; cin >> l >> r;
      l --; r --;
      cout << T.get(1, 0, off, l, r + 1).sum << "\n";
    }
  }
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14840 KB Output is correct
2 Correct 69 ms 15224 KB Output is correct
3 Correct 96 ms 15740 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 18036 KB Output is correct
2 Correct 686 ms 19692 KB Output is correct
3 Correct 631 ms 19664 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 21800 KB Output is correct
2 Correct 1402 ms 24028 KB Output is correct
3 Correct 1295 ms 24440 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2491 ms 29568 KB Output is correct
2 Correct 2272 ms 30156 KB Output is correct
3 Correct 2309 ms 30604 KB Output is correct