oj.uz

Submission #658197

# Submission time Handle Problem Language Result Execution time Memory
658197 2022-11-12T11:18:01 Z bebra Garaža (COCI17_garaza) C++17
160 / 160
 1153 ms 117500 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;

const int MAX_LOG = 35;

struct Segment {
    int l;
    int r;
    int value;

    Segment(int _l = 0, int _r = 0, int _value = 0)
        : l(_l), r(_r), value(_value) {}

    long long len() const {
        return r - l + 1;
    }
};

void merge(vector<Segment>& segs) {
    vector<Segment> new_segs;
    new_segs.reserve(MAX_LOG);
    int n = segs.size();
    for (int i = 0; i < n; ++i) {
        int j = i;
        int l = segs[i].l;
        int r = segs[i].r;
        while (j + 1 < n && segs[i].value == segs[j + 1].value) {
            ++j;
            r = segs[j].r;
        }
        new_segs.emplace_back(l, r, segs[i].value);
        i = j;
    }
    swap(segs, new_segs);
}

struct Node {
    vector<Segment> pref;
    vector<Segment> suf;
    long long cnt;
    int size;

    Node(int _cnt = 0, int _size = 1) {
        cnt = _cnt;
        size = _size;
    }

    void apply(int l, int value) {
        pref.clear();
        suf.clear();
        pref.emplace_back(l, l, value);
        suf.emplace_back(l, l, value);
        if (value <= 1) {
            cnt = 0;
        } else {
            cnt = 1;
        }
    }

    friend Node combine(const Node& lhs, const Node& rhs) {
        if (lhs.cnt == -1) {
            return rhs;
        }
        if (rhs.cnt == -1) {
            return lhs;
        }
        Node new_node;
        new_node.cnt = lhs.cnt + rhs.cnt;
        new_node.size = lhs.size + rhs.size;
        int j = 0;
        int curr_size = lhs.size;
        for (int i = 0; i < (int)rhs.pref.size(); ++i) {
            while (j < (int)lhs.suf.size() && gcd(lhs.suf[j].value, rhs.pref[i].value) == 1) {
                curr_size -= lhs.suf[j].len();
                ++j;
            }
            new_node.cnt += rhs.pref[i].len() * curr_size;
        }
        new_node.pref.reserve(MAX_LOG);
        new_node.suf.reserve(MAX_LOG);
        new_node.pref = lhs.pref;
        for (int i = 0; i < (int)rhs.pref.size(); ++i) {
            new_node.pref.emplace_back(rhs.pref[i].l, rhs.pref[i].r, gcd(lhs.pref.back().value, rhs.pref[i].value));
        }
        merge(new_node.pref);
        for (int i = 0; i < (int)lhs.suf.size(); ++i) {
            new_node.suf.emplace_back(lhs.suf[i].l, lhs.suf[i].r, gcd(lhs.suf[i].value, rhs.suf[0].value));
        }
        new_node.suf.insert(new_node.suf.end(), rhs.suf.begin(), rhs.suf.end());
        // for (int i = 0; i < (int)rhs.suf.size(); ++i) {
        //     new_node.suf.push_back(rhs.suf[i]);
        // }
        merge(new_node.suf);
        return new_node;
    }
};

const int MAX_N = 1e5;
Node tree[MAX_N * 4];
int sz;

inline void build(int l, int r, int v, const vector<int>& a) {
    if (l == r - 1) {
        if (l >= (int)a.size()) {
            tree[v] = Node(-1);
        } else {
            tree[v].apply(l, a[l]);
        }
        return;
    }
    int m = (l + r) / 2;
    build(l, m, 2 * v + 1, a);
    build(m, r, 2 * v + 2, a);
    tree[v] = combine(tree[2 * v + 1], tree[2 * v + 2]);
}

inline void init(const vector<int>& a) {
    sz = 1 << (__lg(a.size()) + 1);
    build(0, sz, 0, a);
}

inline void update(int pos, int value) {
    int v = pos + sz - 1;
    tree[v].apply(pos, value);
    while (v > 0) {
        v = (v - 1) / 2;
        tree[v] = combine(tree[2 * v + 1], tree[2 * v + 2]);
    }
}

inline Node query(int l, int r, int v, int lq, int rq) {
    if (lq <= l && r <= rq) {
        return tree[v];
    } else if (l >= rq || r <= lq) {
        return Node(-1);
    }
    int m = (l + r) / 2;
    return combine(query(l, m, 2 * v + 1, lq, rq), query(m, r, 2 * v + 2, lq, rq));
}

inline long long query(int lq, int rq) {
    return query(0, sz, 0, lq, rq).cnt;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    init(a);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int pos, value;
            cin >> pos >> value;
            --pos;
            update(pos, value);
        } else {
            int l, r;
            cin >> l >> r;
            --l, --r;
            cout << query(l, r + 1) << '\n';
        }
    }
    return 0;
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26196 KB Output is correct
2 Correct 29 ms 28116 KB Output is correct
3 Correct 52 ms 29908 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 43656 KB Output is correct
2 Correct 266 ms 53028 KB Output is correct
3 Correct 255 ms 52796 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 71168 KB Output is correct
2 Correct 594 ms 71336 KB Output is correct
3 Correct 560 ms 80256 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 117500 KB Output is correct
2 Correct 1153 ms 117104 KB Output is correct
3 Correct 972 ms 116932 KB Output is correct