oj.uz

Submission #342722

# Submission time Handle Problem Language Result Execution time Memory
342722 2021-01-02T16:46:29 Z phathnv Garaža (COCI17_garaza) C++11
0 / 160
 451 ms 262144 KB 
#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 <= 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;
    }
};

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);
        } else {
            int l, r;
            cin >> l >> r;
            cout << st.get(l, r) << '\n';
        }
    }

    return 0;
}

Subtask #1
0 / 40.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 150 ms 86336 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 203 ms 213868 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 451 ms 262144 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -