Submission #590726

#	Time	Username	Problem	Language	Result	Execution time	Memory
590726		Loki_Nguyen	Garaža (COCI17_garaza)	C++14	0 / 160	739 ms	39500 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;
};
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.empty() ? 0 : x.L.back().fi;
        res.L = x.L;
        for(pii u: y.L)
        {
            v = __gcd(v, u.fi);
            if(!res.L.empty() && v == res.L.back().fi)continue;
            res.L.pb({v, u.se});
        }
        v = y.R.empty() ? 0 : y.R.back().fi;
        res.R = y.R;
        for (pii u : x.R)
        {
            v = __gcd(v, u.fi);
            if (!res.R.empty() && v == res.R.back().fi)continue;
            res.R.pb({v, u.se});
        }
        if(x.R.empty() || y.L.empty() || __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[j].se+1 : y.L[j+1].se - y.L[j].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.clear();
            st[id].R.clear();
            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;
        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(mid >= v)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(l, r).val << '\n';
    }

}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
#define task "tests"
    if (fopen(task ".in", "r"))
    {
        freopen(task ".in", "r", stdin);
        // freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    // cin >> ntest;
    while (ntest-- > 0)
        sol();
}

Compilation message (stderr)

garaza.cpp: In function 'int32_t main()':
garaza.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen(task ".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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