Submission #591260

#	Time	Username	Problem	Language	Result	Execution time	Memory
591260		Loki_Nguyen	Garaža (COCI17_garaza)	C++14	160 / 160	945 ms	40120 KiB

garaza

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, int>
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back

const int N = 2e5 + 3;
const int M = 1 << 24;
const int mod = 1e4 + 7;
const int base = 300;
const ll inf = 1e12;
int pw(int k, int n)
{
    int total = 1;
    for (; n; n >>= 1)
    {
        if (n & 1)
            total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
int m, n, t, k, a[N], ans, b[N], c[N], d[N];
int dp[N], tong;
vector<int> zero;
struct node
{
    vector<pii> L, R;
    ll val;
    node()
    {
        L.clear();
        R.clear();
        val = 0;
    }
};
struct IT
{
    int n;
    vector<node> st;
    IT(int _n)
    {
        n = _n;
        st.resize(n * 4 + 4);
    }
    node merga(node x, node y, int l, int r)
    {
        node res;
        res.val = x.val + y.val;
        int v = x.L.back().fi;
        res.L = x.L;
        for (pii u : y.L)
        {
            v = __gcd(v, u.fi);
            if (v == res.L.back().fi)
                continue;
            res.L.pb({v, u.se});
        }
        v = y.R.back().fi;
        res.R = y.R;
        for (pii u : x.R)
        {
            v = __gcd(v, u.fi);
            if (v == res.R.back().fi)
                continue;
            res.R.pb({v, u.se});
        }
        if (__gcd(x.R[0].fi, y.L[0].fi) == 1)
        {
            // cout << l <<" "<<r<<" "<<res.val<<'\n';
            return res;
        }

        int j = 0;
        while (j + 1 < (int)y.L.size() && __gcd(x.R[0].fi, y.L[j + 1].fi) > 1)
            ++j;
        for (int i = 0; i < (int)x.R.size(); i++)
        {
            while (j >= 0 && __gcd(x.R[i].fi, y.L[j].fi) == 1)
                --j;
            if (j < 0)
                break;
            res.val += 1ll * (i == (int)x.R.size() - 1 ? x.R[i].se - l + 1 : x.R[i].se - x.R[i + 1].se) * (j == (int)y.L.size() - 1 ? r - y.L[0].se + 1 : y.L[j + 1].se - y.L[0].se);
        }
        // cout << l << " " << r << " " << res.val << '\n';
        return res;
    }

    void build(int id, int l, int r)
    {
        if (l == r)
        {
            st[id].L.pb({a[l], l});
            st[id].R.pb({a[l], l});
            st[id].val = (a[l] > 1);
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        st[id] = merga(st[id << 1], st[id << 1 | 1], l, r);
    }
    void build()
    {
        build(1, 1, n);
    }
    void update(int id, int l, int r, int pos)
    {
        if (l == r)
        {
            st[id].L[0].fi = a[l];
            st[id].R[0].fi = a[l];
            st[id].val = (a[l] > 1);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(id << 1, l, mid, pos);
        else
            update(id << 1 | 1, mid + 1, r, pos);
        st[id] = merga(st[id << 1], st[id << 1 | 1], l, r);
    }
    void update(int pos)
    {
        update(1, 1, n, pos);
    }
    node get(int id, int l, int r, int u, int v)
    {
        if (u <= l && r <= v)
        {
            // cout << l << " " << r<<" " << st[id].val <<'\n';
            return st[id];
        }
        int mid = (l + r) >> 1;
        if (v <= mid)
            return get(id << 1, l, mid, u, v);
        if (mid + 1 <= u)
            return get(id << 1 | 1, mid + 1, r, u, v);
        return merga(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v), max(l, u), min(r, v));
    }
    node get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }
};
void sol()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    IT it(n);
    it.build();
    while (m-- > 0)
    {
        int l, r;
        cin >> t >> l >> r;
        if (t == 1)
        {
            a[l] = r;
            it.update(l);
        }
        else
        {
            //cout << it.get(1, n).val <<" ";
            cout << it.get(l, r).val << '\n';
        }
            
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
#define task "tests"
    if (fopen(task ".inp", "r"))
    {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    int ntest = 1;
    // cin >> ntest;
    while (ntest-- > 0)
        sol();
}
/*
10 10
259008492 685257993 684081919 849336162 185724174 230558609 147159919 225162936 734023603 130213023
2 1 4
2 4 7
2 2 8
2 4 10
2 5 8
2 5 6
2 1 10
2 3 8
2 1 8
2 2 4
2 1 6
*/

Compilation message (stderr)

garaza.cpp: In function 'int main()':
garaza.cpp:181:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:182:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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