oj.uz

Submission #776635

# Submission time Handle Problem Language Result Execution time Memory
776635 2023-07-08T06:19:43 Z mrwang Garaža (COCI17_garaza) C++14
0 / 160
 888 ms 43612 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(cur,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;
        if(o.suf.size()>0) cur=o.suf.back().fi;
        for(int i=0;i<suf.size();i++)
        {
            if(ans.suf.size()==0)
            {
                cur=suf[i].fi;
                ans.suf.pb(suf[i]);
            }
            else
            {
                cur=__gcd(cur,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 l=0,r=0;
        for(int i=0;i<suf.size();i++) l+=suf[i].se;
        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*l;
            l-=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';
        }
    }
}
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:50: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]
   50 |         for(int i=0;i<suf.size();i++)
      |                     ~^~~~~~~~~~~
garaza.cpp:73: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]
   73 |         for(int i=0;i<suf.size();i++) l+=suf[i].se;
      |                     ~^~~~~~~~~~~
garaza.cpp:76: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]
   76 |             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:98:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |     ll mid=l+r>>1;
      |            ~^~
garaza.cpp: In function 'node get(ll, ll, ll, ll, ll)':
garaza.cpp:108:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |     ll mid=l+r>>1;
      |            ~^~

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 22356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 167 ms 26836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 435 ms 32828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 888 ms 43612 KB Output isn't correct
2 Halted 0 ms 0 KB -