| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 468392 | julian33 | Horses (IOI15_horses) | C++14 | 0 ms | 0 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;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxN=5e5+5; //make sure this is right
const int mod=1e9+7;
#define double long double
ll fpow(ll b,ll e){
ll res=1;
while(e){
if(e&1)
res=(res*b)%mod;
b=(b*b)%mod;
e>>=1;
}
return res;
}
ll divmod(ll a,ll b){
return (a*fpow(b,mod-2))%mod;
}
ll st[4*mxN],lazy[4*mxN],x[mxN],y[mxN],n,psa2[mxN];
double st2[4*mxN],lazy2[4*mxN],psa[mxN];
void mul(ll &a,ll b){a=(a*b)%mod;}
void build(int v,int l,int r){
if(l==r){
st2[v]=psa[l]+log10(y[l]);
st[v]=(psa2[l]*y[l])%mod;
} else{
int m=(l+r)>>1;
build(v<<1,l,m);
build(v<<1|1,m+1,r);
st2[v]=max(st2[v<<1],st2[v<<1|1]);
}
}
void push(int v){
mul(st[v<<1],lazy[v]);
mul(st[v<<1|1],lazy[v]);
mul(lazy[v<<1],lazy[v]);
mul(lazy[v<<1|1],lazy[v]);
lazy[v]=1;
st2[v<<1]+=lazy2[v];
st2[v<<1|1]+=lazy2[v];
lazy2[v<<1]+=lazy2[v];
lazy2[v<<1|1]+=lazy2[v];
lazy2[v]=0;
}
void range_upd(int v,int l,int r,int lq,int rq,ll v1,double v2){
if(lq>rq)
return;
if(l>=lq && r<=rq){
st[v]=(st[v]*v1)%mod;
st2[v]+=v2;
lazy2[v]+=v2;
lazy[v]=(lazy[v]*v1)%mod;
} else{
int m=(l+r)>>1;
push(v);
range_upd(v<<1,l,m,lq,min(rq,m),v1,v2);
range_upd(v<<1|1,m+1,r,max(lq,m+1),rq,v1,v2);
st2[v]=max(st2[v<<1],st2[v<<1|1]);
}
}
void point_upd(int v,int l,int r,int ind,ll v1,double v2){
if(l>ind || r<ind)
return;
if(l==r){
mul(st[v],v1);
st2[v]+=v2;
} else{
int m=(l+r)>>1;
push(v);
point_upd(v<<1,l,m,ind,v1,v2);
point_upd(v<<1|1,m+1,r,ind,v1,v2);
st2[v]=max(st2[v<<1],st2[v<<1|1]);
}
}
int get(int v,int l,int r){
deb(l,r,st[v]);
if(l==r)
return st[v];
push(v);
int m=(l+r)>>1;
if(st2[v<<1]>st2[v<<1|1])
return get(v<<1,l,m);
return get(v<<1|1,m+1,r);
}
int init(int N, int X[], int Y[]){
n=N;
psa2[0]=1;
for(int i=1;i<=n;i++){
x[i]=X[i-1];
y[i]=Y[i-1];
psa[i]=psa[i-1]+log10(x[i]);
psa2[i]=(psa2[i-1]*x[i])%mod;
}
fill(lazy+1,lazy+1+4*n,1);
build(1,1,n);
return get(1,1,n);
}
int updateX(int pos, int val){
pos++;
ll v=divmod(val,x[pos]);
double v2=log10(val)-log10(x[pos]);
x[pos]=val;
range_upd(1,1,n,pos,n,v,v2);
return get(1,1,n);
}
int updateY(int pos,int val){
pos++;
ll v=divmod(val,y[pos]);
double v2=log10(val)-log10(y[pos]);
y[pos]=val;
point_upd(1,1,n,pos,v,v2);
return get(1,1,n);
}
int main(){
cin.sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int N; cin>>N;
int X[N],Y[N];
for(int i=0;i<N;i++)
cin>>X[i];
for(int i=0;i<N;i++)
cin>>Y[i];
cout<<init(N,X,Y)<<"\n";
int q; cin>>q;
while(q--){
int op,a,b; cin>>op>>a>>b;
if(op==1)
cout<<updateX(a,b)<<"\n";
else
cout<<updateY(a,b)<<"\n";
}
}