Submission #745599

#	Time	Username	Problem	Language	Result	Execution time	Memory
745599		bgnbvnbv	Relativnost (COCI15_relativnost)	C++14	140 / 140	1060 ms	23028 KiB

relativnost

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#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=10007;
ll c;
struct node
{
    int dp[20];
    node()
    {
        for(int i=0;i<c;i++) dp[i]=0;
    }
    node operator+(const node&o)
    {
        node ans;
        for(int i=0;i<c;i++)
        {
            for(int j=0;j<=i;j++)
            {
                ans.dp[i]+=1ll*dp[j]*o.dp[i-j]%mod;
                if(ans.dp[i]>=mod) ans.dp[i]-=mod;
            }
        }
        return ans;
    }
}st[4*maxN];
ll n,a[maxN],b[maxN];
ll pw(ll x,ll y)
{
    if(y==0) return 1;
    ll x1=pw(x,y/2);
    x1=x1*x1%mod;
    if(y&1) x1=x1*x%mod;
    return x1;
}
void build(ll id=1,ll l=1,ll r=n)
{
    if(l==r)
    {
        st[id]=node();
        st[id].dp[0]=b[l];
        st[id].dp[1]=a[l];
        return;
    }
    ll mid=l+r>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
void update(ll pos,ll val1,ll val2,ll id=1,ll l=1,ll r=n)
{
    if(l==r)
    {
        st[id].dp[0]=val2;
        st[id].dp[1]=val1;
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(pos,val1,val2,id*2,l,mid);
    else update(pos,val1,val2,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
ll q;
void solve()
{
    cin >> n >> c;
    ll ans=1;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> b[i],ans*=(b[i]+a[i]),ans%=mod;
    build();
    cin >> q;
    for(int i=1;i<=q;i++)
    {
        ll p,x,y;
        cin >> p >> x >> y;
        ll sum=(a[p]+b[p])%mod;
        ans=ans*pw(sum,mod-2);
        ans%=mod;
        a[p]=x;
        b[p]=y;
        ans=ans*(a[p]+b[p]);
        ans%=mod;
        update(p,x,y);
        ll vd=0;
        for(int j=0;j<c;j++)
        {
            vd+=st[1].dp[j];
            if(vd>=mod) vd-=mod;
        }
        if(ans-vd<0) cout << ans-vd+mod<<'\n';
        else cout << ans-vd<<'\n';
    }
    //cout << st[2].dp[2]<<'\n';
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

relativnost.cpp: In function 'void build(ll, ll, ll)':
relativnost.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     ll mid=l+r>>1;
      |            ~^~
relativnost.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
relativnost.cpp:66:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     ll mid=l+r>>1;
      |            ~^~

• Subtask 1: 140 / 140