| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 163594 | knon0501 | 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;
long double seg[2000001];
long double lazy[2000001];
long double x[500001];
long double s[500001];
long double y[500001];
const long long D=1e9+7;
int n,m,nn;
long long pow2(long long x,long long y){
if(y==0)return 1;
long long k=pow2(x,y/2);
if(y%2)return k*k%D*x%D;
return k*k%D;
}
int f(long double x){
long long y=(long long)x;
long double k=x-y;
long long ret=pow2(10,y);
long double z=pow(10,k);
return ((long long)round(z*ret))%D;
}
void upd(int lef,int rig,int x,int y,int lev,long double k){
seg[lev]+=lazy[lev];
if(lev<nn){
lazy[lev*2]+=lazy[lev];
lazy[lev*2+1]+=lazy[lev];
}
lazy[lev]=0;
if(lef>y || x>rig)return;
if(x<=lef && rig<=y){
seg[lev]+=k;
if(lev<nn){
lazy[lev*2]+=k;
lazy[lev*2+1]+=k;
}
return;
}
int mid=(lef+rig)/2;
upd(lef,mid,x,y,lev*2,k);
upd(mid+1,rig,x,y,lev*2+1,k);
seg[lev]=max(seg[lev*2],seg[lev*2+1]);
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n;
for(nn=1 ; nn<n ; nn*=2);
int i,j;
for(i=0 ; i<n; i++){
cin>>x[i];
x[i]=log10(x[i]);
if(i>0)
s[i]=s[i-1]+x[i];
else
s[i]=x[i];
}
for(i=0 ; i<n ; i++){
cin>>y[i];
y[i]=log10(y[i]);
}
for(i=0 ; i<n ; i++){
seg[nn+i]=s[i]+y[i];
}
for(i=nn-1 ; i>=1 ; i--){
seg[i]=max(seg[i*2],seg[i*2+1]);
}
///cout<<seg[1]<<"\n";
cout<<f(seg[1])<<"\n";
cin>>m;
for(i=0 ; i<m ; i++){
int q,w,e;
cin>>q>>w>>e;
if(q==1){
upd(0,nn-1,w,n-1,1,log10((double)e)-x[w]);
x[w]=log10((double)e);
}
else{
upd(0,nn-1,w,w,1,log10((double)e)-y[w]);
y[w]=log10((double)e);
}
cout<<f(seg[1]);
}
return 0;
}