oj.uz

Submission #658176

# Submission time Handle Problem Language Result Execution time Memory
658176 2022-11-12T10:35:44 Z bebra Garaža (COCI17_garaza) C++17
0 / 160
 4000 ms 42900 KB 
#include <bits/stdc++.h>
using namespace std;

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


struct SegmentTree {
    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;
        }
    };

    friend void merge(vector<Segment>& segs) {
        vector<Segment> new_segs;
        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 = 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.back().value));
            }
            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;
        }
    };

    vector<Node> tree;
    int size;

    SegmentTree(const vector<int>& a) {
        size = a.size();
        size = 1 << (__lg(a.size()) + 1);
        tree.resize(2 * size - 1);
        build(0, size, 0, a);
    }

    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]);
    }

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

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

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


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;
    SegmentTree segtree(a);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int pos, value;
            cin >> pos >> value;
            --pos;
            segtree.update(pos, value);
        } else {
            int l, r;
            cin >> l >> r;
            --l, --r;
            cout << segtree.query(l, r + 1) << '\n';
        }
    }
    return 0;
}

Subtask #1
0 / 40.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4088 ms 21588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4078 ms 42900 KB Time limit exceeded
2 Halted 0 ms 0 KB -