oj.uz

Submission #342707

# Submission time Handle Problem Language Result Execution time Memory
342707 2021-01-02T16:31:01 Z phathnv Garaža (COCI17_garaza) C++11
40 / 160
 4000 ms 1680 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 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];

    while (q--){
        int type;
        cin >> type;
        if (type == 1){
            int pos, val;
            cin >> pos >> val;
            a[pos] = val;
        } else {
            int l, r;
            cin >> l >> r;
            node valL(-1, -1), valR(-1, -1);
            int mid = (l + r) >> 1;
            for(int i = l; i <= mid; i++)
                valL = valL + node(i, a[i]);
            for(int i = mid + 1; i <= r; i++)
                valR = valR + node(i, a[i]);

            cout << (valL + valR).cnt << '\n';
        }
    }

    return 0;
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 364 KB Output is correct
2 Correct 773 ms 496 KB Output is correct
3 Correct 1512 ms 620 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4070 ms 1100 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 4061 ms 1680 KB Time limit exceeded
2 Halted 0 ms 0 KB -