oj.uz

Submission #235422

# Submission time Handle Problem Language Result Execution time Memory
235422 2020-05-28T09:00:12 Z VEGAnn Garaža (COCI17_garaza) C++14
160 / 160
 2714 ms 80792 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define MP make_pair
#define ft first
#define sd second
#define PB push_back
#define pli pair<ll,int>
#define pii pair<int,int>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
const int N = 100100;
const int PW = 22;
const int oo = 2e9;
map<int,int>::iterator ite, ste;
int n, q, a[N];

struct seg{
    ll ans;
    int len;
    map<int, int> pref, suf;

    seg(): ans(0), len(0) {
        pref.clear();
        suf.clear();
    }
};

seg st[4 * N];

seg combine(seg lf, seg rt){
    seg res;

//    cerr << lf.len << " " << rt.len << '\n';

    res.ans = lf.ans + rt.ans;
    res.len = lf.len + rt.len;

    ite = lf.suf.begin();
    ste = rt.pref.begin();

//    for (auto x : rt.pref)
//        cerr << x.ft << " " << x.sd << '\n';

    while (ste != rt.pref.end()){
        int sls = rt.len;

        if (next(ste) != rt.pref.end())
            sls = (*next(ste)).sd;

        pii cur = *ste;

        while (1){
            pii scr = *ite;

            if (__gcd(scr.ft, -cur.ft) > 1) break;

            ite++;

            if (ite == lf.suf.end()) break;
        }

        if (ite != lf.suf.end())
            res.ans += (ll)(lf.len - (*ite).sd) * (ll)(sls - cur.sd);
        else break;

        ste++;
    }

    res.pref = lf.pref;
    ste = rt.pref.begin();

    int gc = -(*(--lf.pref.end())).ft;

    while (ste != rt.pref.end() && gc > 1){
        pii cur = *ste;

        int ngc = __gcd(gc, -cur.ft);

        if (gc != ngc){
            gc = ngc;
            res.pref[-gc] = lf.len + cur.sd;
        }

        ste++;
    }

    for (auto x : rt.suf)
        res.suf[x.ft] = x.sd + lf.len;

    gc = (*rt.suf.begin()).ft;
    ite = (--lf.suf.end());

    while (1){
        pii cur = *ite;

        gc = __gcd(gc, cur.ft);

        res.suf[gc] = cur.sd;

        if (ite == lf.suf.begin()) break;

        ite--;
    }

    return res;
}

void build(int v, int l, int r){
    if (l == r){
        st[v].ans = bool(a[l] > 1);
        st[v].len = 1;
        st[v].pref[-a[l]] = 0;
        st[v].suf[a[l]] = 0;
        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    st[v] = combine(st[v + v], st[v + v + 1]);
}

void update(int v, int l, int r, int ps){
    if (l == r){
        st[v].ans = bool(a[l] > 1);
        st[v].len = 1;

        st[v].pref.clear();
        st[v].suf.clear();

        st[v].pref[-a[l]] = 0;
        st[v].suf[a[l]] = 0;
        return;
    }

    int md = (l + r) >> 1;

    if (ps <= md)
        update(v + v, l, md, ps);
    else update(v + v + 1, md + 1, r, ps);

    st[v] = combine(st[v + v], st[v + v + 1]);
}

seg calc(int v, int tl, int tr, int l, int r){
    if (tl == l && tr == r) return st[v];

    int md = (tl + tr) >> 1;

    if (r <= md)
        return calc(v + v, tl, md, l, r);
    else if (l > md)
        return calc(v + v + 1, md + 1, tr, l, r);
    else return combine(calc(v + v, tl, md, l, min(r, md)),
                        calc(v + v + 1, md + 1, tr, max(md + 1, l), r));
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> q;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    build(1, 0, n - 1);

    for (; q; q--){
        int tp; cin >> tp;

        if (tp == 1){
            int ps, x; cin >> ps >> x;
            ps--; a[ps] = x;

            update(1, 0, n - 1, ps);
        } else {
            int l, r; cin >> l >> r;
            l--; r--;

            cout << calc(1, 0, n - 1, l, r).ans << '\n';
        }
    }

    return 0;
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 44672 KB Output is correct
2 Correct 70 ms 45368 KB Output is correct
3 Correct 96 ms 45944 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 51576 KB Output is correct
2 Correct 591 ms 55184 KB Output is correct
3 Correct 509 ms 54264 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1444 ms 62456 KB Output is correct
2 Correct 1324 ms 60812 KB Output is correct
3 Correct 1142 ms 64508 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2523 ms 80792 KB Output is correct
2 Correct 2714 ms 79008 KB Output is correct
3 Correct 2063 ms 77864 KB Output is correct