Submission #342728

#	Time	Username	Problem	Language	Result	Execution time	Memory
342728		phathnv	Garaža (COCI17_garaza)	C++11	160 / 160	1107 ms	213512 KiB

garaza

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct node{
    ll cnt;
    int l, r, szLeft, szRight;
    pair <int, int> valLeft[32], valRight[32];
    node(int pos = 0, int val = 0){
        l = r = pos;
        cnt = (val > 1);
        szLeft = szRight = 1;
        valLeft[1] = {pos, val};
        valRight[1] = {pos, val};
        valLeft[2] = {pos + 1, 1};
        valRight[2] = {pos - 1, 1};
    }
    node operator + (const node &oth){
        if (l == -1 && r == -1)
            return oth;
        if (oth.l == -1 && oth.r == -1)
            return (*this);

        node res;
        res.cnt = cnt + oth.cnt;
        res.l = l;
        res.r = oth.r;
        res.szLeft = szLeft;
        res.szRight = oth.szRight;
        for(int i = 1; i <= szLeft; i++)
            res.valLeft[i] = valLeft[i];
        for(int i = 1; i <= oth.szRight; i++)
            res.valRight[i] = oth.valRight[i];

        int ptr = 1;
        for(int i = szRight; i >= 1; i--){
            while (ptr <= oth.szLeft && __gcd(valRight[i].second, oth.valLeft[ptr].second) > 1)
                ptr++;
            res.cnt += (ll) (valRight[i].first - valRight[i + 1].first) * (oth.valLeft[ptr].first - oth.valLeft[1].first);
        }
        for(int i = 1; i <= oth.szLeft; i++){
            pair <int, int> tmp = {oth.valLeft[i].first, __gcd(res.valLeft[res.szLeft].second, oth.valLeft[i].second)};
            if (tmp.second != res.valLeft[res.szLeft].second)
                res.valLeft[++res.szLeft] = tmp;
        }
        for(int i = 1; i <= szRight; i++){
            pair <int, int> tmp = {valRight[i].first, __gcd(res.valRight[res.szRight].second, valRight[i].second)};
            if (tmp.second != res.valRight[res.szRight].second)
                res.valRight[++res.szRight] = tmp;
        }
        res.valLeft[res.szLeft + 1] = {res.r + 1, 1};
        res.valRight[res.szRight + 1] = {res.l - 1, 1};
        return res;
    }
};

struct segmentTree{
    int n;
    vector <node> d;
    void build(int id, int l, int r, vector <int> &a){
        if (l == r){
            d[id] = node(l, a[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid, a);
        build(id << 1 | 1, mid + 1, r, a);
        d[id] = d[id << 1] + d[id << 1 | 1];
    }
    void update(int id, int l, int r, int pos, int val){
        if (pos < l || r < pos)
            return;
        if (l == r){
            d[id] = node(pos, val);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, pos, val);
        update(id << 1 | 1, mid + 1, r, pos, val);
        d[id] = d[id << 1] + d[id << 1 | 1];
    }
    node get(int id, int l, int r, int u, int v){
        if (v < l || r < u)
            return node(-1, -1);
        if (u <= l && r <= v)
            return d[id];
        int mid = (l + r) >> 1;
        return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
    }

    segmentTree(int _n, vector <int> &a){
        n = _n;
        d.resize(n * 4 + 1);
        build(1, 1, n, a);
    }
    void update(int pos, int val){
        update(1, 1, n, pos, val);
    }
    ll get(int l, int r){
        return get(1, 1, n, l, r).cnt;
    }
};

node Calc(int l, int r, vector <int> &a){
    if (l == r)
        return node(l, a[l]);
    int mid = (l + r) >> 1;
    return Calc(l, mid, a) + Calc(mid + 1, r, a);
}

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

    int n, q;
    cin >> n >> q;
    vector <int> a(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    segmentTree st(n, a);
    while (q--){
        int type;
        cin >> type;
        if (type == 1){
            int pos, val;
            cin >> pos >> val;
            st.update(pos, val);
            a[pos] = val;
        } else {
            int l, r;
            cin >> l >> r;
            cout << st.get(l, r) << '\n';
            //cout << Calc(l, r, a).cnt << '\n';
        }
    }

    return 0;
}

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40
• Subtask 4: 40 / 40