Submission #776651

#	Time	Username	Problem	Language	Result	Execution time	Memory
776651		mrwang	Garaža (COCI17_garaza)	C++14	160 / 160	855 ms	44480 KiB

garaza

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
struct node
{
    vector<pli>pre,suf;
    ll cnt;
    node ()
    {
        cnt=0;
    }
    node operator+(const node&o)
    {
        node ans;
        ll cur=0;
        if(pre.size()>0) cur=pre.back().fi;
        ans.pre=pre;
        for(int i=0;i<o.pre.size();i++)
        {
            if(ans.pre.size()==0)
            {
                cur=o.pre[i].fi;
                ans.pre.pb(o.pre[i]);
            }
            else
            {
                cur=__gcd(ans.pre.back().fi,o.pre[i].fi);
                if(cur==ans.pre.back().fi)
                {
                    ans.pre.back().se+=o.pre[i].se;
                }
                else
                {
                    ans.pre.pb({cur,o.pre[i].se});
                }
            }
        }
        ans.suf=o.suf;
        cur=0;
        for(int i=0;i<suf.size();i++)
        {
            if(ans.suf.size()==0)
            {
                ans.suf.pb(suf[i]);
            }
            else
            {
                cur=__gcd(ans.suf.back().fi,suf[i].fi);
                if(cur==ans.suf.back().fi)
                {
                    ans.suf.back().se+=suf[i].se;
                }
                else
                {
                    ans.suf.pb({cur,suf[i].se});
                }
            }
        }
        ans.cnt=cnt+o.cnt;
        ll j=0;
        ll r=0;
        for(int i=(int)suf.size()-1;i>=0;i--)
        {
            while(j<o.pre.size()&&__gcd(o.pre[j].fi,suf[i].fi)>1)
            {
                r+=o.pre[j].se;
                j++;
            }
            ans.cnt+=r*suf[i].se;
        }
        return ans;
    }
}st[4*maxN];
ll n;
void update(ll pos,ll val,ll id=1,ll l=1,ll r=n)
{
    if(l==r)
    {
        st[id]=node();
        st[id].pre.pb({val,1});
        st[id].suf.pb({val,1});
        st[id].cnt+=(val>1);
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(pos,val,id*2,l,mid);
    else update(pos,val,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}

node get(ll i,ll j,ll id=1,ll l=1,ll r=n)
{
    if(j<l||r<i) return node();
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r);
}
void solve()
{
    ll q,x;
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> x,update(i,x);
    while(q--)
    {
        ll t;
        cin >> t;
        if(t==1)
        {
            ll pos,val;
            cin >> pos >> val;
            update(pos,val);
        }
        else
        {
            ll i,j;
            cin >> i >> j;
            cout << get(i,j).cnt<<'\n';
        }
    }
    //for(auto zz:st[1].pre)
    {
        //cout << zz.fi<<' '<<zz.se<<'\n';
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

garaza.cpp: In member function 'node node::operator+(const node&)':
garaza.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int i=0;i<o.pre.size();i++)
      |                     ~^~~~~~~~~~~~~
garaza.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int i=0;i<suf.size();i++)
      |                     ~^~~~~~~~~~~
garaza.cpp:73:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             while(j<o.pre.size()&&__gcd(o.pre[j].fi,suf[i].fi)>1)
      |                   ~^~~~~~~~~~~~~
garaza.cpp: In function 'void update(ll, ll, ll, ll, ll)':
garaza.cpp:94:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     ll mid=l+r>>1;
      |            ~^~
garaza.cpp: In function 'node get(ll, ll, ll, ll, ll)':
garaza.cpp:104:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |     ll mid=l+r>>1;
      |            ~^~

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