oj.uz

Submission #776651

# Submission time Handle Problem Language Result Execution time Memory
776651 2023-07-08T06:35:33 Z mrwang Garaža (COCI17_garaza) C++14
160 / 160
 855 ms 44480 KB 
#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

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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22356 KB Output is correct
2 Correct 26 ms 22768 KB Output is correct
3 Correct 34 ms 23244 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 26332 KB Output is correct
2 Correct 243 ms 28416 KB Output is correct
3 Correct 209 ms 28032 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 31624 KB Output is correct
2 Correct 483 ms 33088 KB Output is correct
3 Correct 460 ms 33868 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 41700 KB Output is correct
2 Correct 847 ms 44480 KB Output is correct
3 Correct 819 ms 41812 KB Output is correct