Submission #240062

#	Time	Username	Problem	Language	Result	Execution time	Memory
240062		Vimmer	Garaža (COCI17_garaza)	C++14	160 / 160	1069 ms	40444 KiB

garaza

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 101001
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9


using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 3> a3;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int gcd(int a, int b)
{
    while (b)
    {
        a %= b;

        swap(a, b);
    }

    return a;
}
struct st
{
    vector <pair <int, int> > pr, sf;

    ll ans;
};

int n, q, a[N];

st t[N * 4];

st combine(st a, st b)
{
    st res;

    res.pr = a.pr;

    for (int i = 0; i < sz(b.pr); i++)
    {
        pair <int, int> cur = b.pr[i];

        int g = gcd(res.pr.back().F, cur.F);

        if (g == res.pr.back().F) res.pr.back().S += cur.S;
          else res.pr.pb({g, cur.S});
    }

    res.sf = b.sf;

    for (int i = 0; i < sz(a.sf); i++)
    {
        pair <int, int> cur = a.sf[i];

        int g = gcd(res.sf.back().F, cur.F);

        if (g == res.sf.back().F) res.sf.back().S += cur.S;
          else res.sf.pb({g, cur.S});
    }

    res.ans = a.ans + b.ans;

    int pr[sz(b.pr)];

    pr[0] = b.pr[0].S;

    for (int i = 1; i < sz(b.pr); i++) pr[i] = pr[i - 1] + b.pr[i].S;

    int j = sz(b.pr) - 1;

    for (int i = 0; i < sz(a.sf); i++)
    {
        pair <int, int> cur = a.sf[i];

        while (1)
        {
            if (j == -1) break;

            int g = gcd(cur.F, b.pr[j].F);

            if (g == 1) j--;
              else break;
        }

        if (j == -1) break;

        res.ans += ll(pr[j]) * ll(cur.S);
    }
    return res;
}

void build(int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v].ans = int(a[tl] > 1);

        t[v].pr.pb({a[tl], 1});

        t[v].sf.pb({a[tl], 1});

        return;
    }

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

    build(v + v, tl, md);

    build(v + v + 1, md + 1, tr);

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

void upd(int v, int tl, int tr, int pos)
{
    if (tl == tr)
    {
        t[v].ans = bool(a[tl] > 1);

        t[v].pr.clear(); t[v].sf.clear();

        t[v].pr.pb({a[tl], 1});

        t[v].sf.pb({a[tl], 1});

        return;
    }

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

    if (pos <= md) upd(v + v, tl, md, pos);
      else upd(v + v + 1, md + 1, tr, pos);

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

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

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

    if (r <= md) return calc(v + v, tl, md, l, r);

    if (md + 1 <= l) return calc(v + v + 1, md + 1, tr, l, r);

    return combine(calc(v + v, tl, md, l, r), calc(v + v + 1, md + 1, tr, l, r));
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;

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

    build(1, 0, n - 1);

    for ( ;q > 0; q--)
    {
        int tp, l, r;

        cin >> tp >> l >> r;

        if (tp == 2) cout << calc(1, 0, n - 1, l - 1, r - 1).ans << '\n';
          else {l--; a[l] = r; upd(1, 0, n - 1, l); }
    }
}

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