# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
98688 | tduong0806 | Relativnost (COCI15_relativnost) | C++14 | 412 ms | 33792 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 int long long
#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];
t[s][0]=b[l];
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];
forinc(i,1,n)
{
cin>>b[i];
T=(T*(a[i]+b[i]))%mod;
}
build(1,1,n);
cin>>q;
while(q--)
{
int i,A,B;
cin>>i>>A>>B;
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |