| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 163594 | knon0501 | 말 (IOI15_horses) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}