oj.uz

Submission #98691

# Submission time Handle Problem Language Result Execution time Memory
98691 2019-02-25T04:07:55 Z tduong0806 Relativnost (COCI15_relativnost) C++14
140 / 140
 1089 ms 24056 KB 
#include<bits/stdc++.h>
using namespace std;
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forv(a,b) for(auto &a:b)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define onbit(x,i) (x|(1<<(i-1)))
#define offbit(x,i) (x&~(1<<(i-1)))
#define read2(a,b) read(a),read(b)
#define read3(a,b,c) read(a),read(b),read(c)
const int N=100010,mod=10007;
int n,c,q,a[N],b[N],T,t[4*N][22];
int pw(int a,int i)
{
    int b=1;
    for(;i;i>>=1,a=a*a%mod) if(i&1) b=b*a%mod;
    return b;
}
void tran(int s)
{
    forinc(i,0,c-1) t[s][i]=0;
    forinc(i,0,c-1) forinc(j,0,c-i-1)
    {
        //cout<<s<<" "<<i<<" "<<j<<" "<<t[2*s][i]<<" "<<t[2*s+1][j]<<endl;
        t[s][i+j]=(t[s][i+j]+t[2*s][i]*t[2*s+1][j])%mod;
    }
}
void build(int s,int l,int r)
{
    if(l==r)
    {
        t[s][1]=a[l]%mod;
        t[s][0]=b[l]%mod;
        return;
    }
    int mid=(l+r)/2;
    build(2*s,l,mid);
    build(2*s+1,mid+1,r);
    tran(s);
}
void update(int s,int l,int r,int u,pii x)
{
    if(u<l||u>r) return;
    if(l==r)
    {
        t[s][1]=x.fi;
        t[s][0]=x.se;
        return;
    }
    int mid=(l+r)/2;
    update(2*s,l,mid,u,x);
    update(2*s+1,mid+1,r,u,x);
    tran(s);
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("RELATIVNOST.inp","r",stdin);
    //freopen("RELATIVNOST.out","w",stdout);
    cin>>n>>c;
    T=1;
    forinc(i,1,n) {cin>>a[i];a[i]%=mod;}
    forinc(i,1,n)
    {
        cin>>b[i];b[i]%=mod;
        T=(T*(a[i]+b[i])%mod)%mod;
    }
    build(1,1,n);
    cin>>q;
    while(q--)
    {
        int i,A,B;
        cin>>i>>A>>B;
        A%=mod;B%=mod;
        T=(T*pw(a[i]+b[i],mod-2)%mod*(A+B))%mod;
        a[i]=A,b[i]=B;
        update(1,1,n,i,{A,B});
        int kq=T;
        forinc(i,0,c-1) kq=(kq-t[1][i])%mod;
        if(kq<0) kq+=mod;
        cout<<kq<<"\n";
    }
}

Compilation message

relativnost.cpp:61:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 9 ms 512 KB Output is correct
3 Correct 9 ms 512 KB Output is correct
4 Correct 203 ms 12408 KB Output is correct
5 Correct 523 ms 24056 KB Output is correct
6 Correct 689 ms 24012 KB Output is correct
7 Correct 346 ms 12476 KB Output is correct
8 Correct 341 ms 23928 KB Output is correct
9 Correct 410 ms 23928 KB Output is correct
10 Correct 1089 ms 23956 KB Output is correct