oj.uz

Submission #98013

# Submission time Handle Problem Language Result Execution time Memory
98013 2019-02-19T18:27:44 Z dalgerok Garaža (COCI17_garaza) C++17
160 / 160
 1641 ms 42648 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 1e5 + 5;


int n, m, a[N];

inline void Add(vector < pair < int, int > > &vec, vector < pair < int, int > > &add){
    int sz = vec.back().first;
    for(auto it : add){
        int val = __gcd(it.second, vec.back().second);
        int cursz = sz + it.first;
        if(val == vec.back().second){
            vec.back().first = cursz;
        }
        else{
            vec.push_back(make_pair(cursz, val));
        }
    }
}
struct Node{
    long long ans;
    vector < pair < int, int > > pref, suf;
    Node(){
        ans = 0;
    }
    Node(int x){
        pref.clear();
        suf.clear();
        pref.push_back(make_pair(0, 0));
        pref.push_back(make_pair(1, x));
        suf.push_back(make_pair(0, 0));
        suf.push_back(make_pair(1, x));
        ans = (x != 1);
    }
};
Node bad, t[4 * N];

inline Node operator + (Node a, Node b){
    if(a.pref.empty()){
        return b;
    }
    if(b.pref.empty()){
        return a;
    }
    Node c;
    c.pref = a.pref;
    c.suf = b.suf;
    Add(c.pref, b.pref);
    Add(c.suf, a.suf);
    c.ans = a.ans + b.ans;
    for(int i = 1, j = (int)b.pref.size() - 1; i < (int)a.suf.size(); i++){
        while(j > 0 && __gcd(a.suf[i].second, b.pref[j].second) == 1){
            j -= 1;
        }
        c.ans += 1LL * (a.suf[i].first - a.suf[i - 1].first) * b.pref[j].first;
    }
    return c;
}

void build(int v, int l, int r){
    if(l == r){
        t[v] = Node(a[l]);
        return;
    }
    int mid = (r + l) >> 1;
    build(v + v, l, mid);
    build(v + v + 1, mid + 1, r);
    t[v] = t[v + v] + t[v + v + 1];
}

void update(int v, int l, int r, int pos, int x){
    if(l == r){
        t[v] = Node(x);
        return;
    }
    int mid = (r + l) >> 1;
    if(pos <= mid){
        update(v + v, l, mid, pos, x);
    }
    else{
        update(v + v + 1, mid + 1, r, pos, x);
    }
    t[v] = t[v + v] + t[v + v + 1];
}

Node get(int v, int l, int r, int tl, int tr){
    if(l > r || l > tr || tl > r){
        return bad;
    }
    if(tl <= l && r <= tr){
        return t[v];
    }
    int mid = (r + l) >> 1;
    return get(v + v, l, mid, tl, tr) + get(v + v + 1, mid + 1, r, tl, tr);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    build(1, 1, n);
    while(m--){
        int type;
        cin >> type;
        if(type == 1){
            int pos, x;
            cin >> pos >> x;
            update(1, 1, n, pos, x);
        }
        else{
            int l, r;
            cin >> l >> r;
            cout << get(1, 1, n, l, r).ans << "\n";
        }
    }
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 22392 KB Output is correct
2 Correct 46 ms 22784 KB Output is correct
3 Correct 65 ms 23288 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 26480 KB Output is correct
2 Correct 311 ms 28312 KB Output is correct
3 Correct 418 ms 27928 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 31796 KB Output is correct
2 Correct 792 ms 32620 KB Output is correct
3 Correct 820 ms 33144 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 41704 KB Output is correct
2 Correct 1526 ms 42648 KB Output is correct
3 Correct 1641 ms 40676 KB Output is correct