| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 194118 | toma | Horses (IOI15_horses) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define M (L+R)/2
#define N 500009
#define inf 99999999999
#define ll long long
#define mod 1000000007
using namespace std;
ll n,m,x[N],y[N],u,pos,X,ANS;
double A,B,T;
pair <double,ll> p;
struct node{
ll nam;
node *left,*right;
node(): nam(1),left(NULL),right(NULL){}
};
node *root(NULL);
void add(node *&parent,ll L,ll R,ll ind){
if(!parent){
parent=new node();
}
if(L+1==R){
parent->nam=x[ind]%mod;
return;
}
if(ind<M){
add(parent->left,L,M,ind);
} else {
add(parent->right,M,R,ind);
}
parent->nam=((parent->left?parent->left->nam:1)*(parent->right?parent->right->nam:1))%mod;
}
ll get(node *&parent,ll L,ll R,ll l,ll r){
if(parent){
if(L>=r || R<=l)return 1;
if(l<=L && R<=r)return parent->nam;
return (get(parent->left,L,M,l,r)*get(parent->right,M,R,l,r))%mod;
}
return 1;
}
struct nod{
pair<double,ll> D;
double b;
nod *left,*right;
nod(): D({0,0}),b(0),left(NULL),right(NULL){}
};
nod *rot(NULL);
void upd(nod *&parent,ll L,ll R,ll ind){
if(!parent){
parent=new nod();
}
if(L+1==R){
parent->D={log(y[ind])+T,ind};
return;
}
if(ind<M){
upd(parent->left,L,M,ind);
} else {
upd(parent->right,M,R,ind);
}
A=B=0;
if(parent->left)A=parent->left->D.f;
if(parent->right)B=parent->right->D.f;
if(A>=B ){
parent->D=parent->left->D;
} else {
parent->D=parent->right->D;
}
}
void ad(nod *&parent,ll L,ll R,ll l,ll r,double x){
if(parent){
if(parent->b!=0){
if(parent->left)parent->left->b+=parent->b;
if(parent->right)parent->right->b+=parent->b;
parent->D.f+=parent->b;
parent->b=0;
}
if(L>=r || R<=l)return;
if(l<=L && R<=r){
if(parent->left)parent->left->b+=x;
if(parent->right)parent->right->b+=x;
parent->D.f+=x;
return;
}
ad(parent->left,L,M,l,r,x);
ad(parent->right,M,R,l,r,x);
A=B=0;
if(parent->left)A=parent->left->D.f;
if(parent->right)B=parent->right->D.f;
if(A>=B){
parent->D=parent->left->D;
} else {
parent->D=parent->right->D;
}
}
}
pair<double,ll> ge(nod *&parent,ll L,ll R,ll l,ll r){
if(parent){
if(parent->b!=0){
if(parent->left)parent->left->b+=parent->b;
if(parent->right)parent->right->b+=parent->b;
parent->D.f+=parent->b;
parent->b=0;
}
if(L>=r || R<=l)return {0,0};
if(l<=L && R<=r)return parent->D;
ge(parent->left,L,M,l,r);
ge(parent->right,M,R,l,r);
}
return {0,0};
}
int main(){
ios::sync_with_stdio(0);
cin>>n;
for(int i=0;i<n;i++){
cin>>x[i];
add(root,0,n,i);
}
T=0;
for(int i=0;i<n;i++){
cin>>y[i];
T+=log(x[i]);
upd(rot,0,n,i);
}
p=rot->D;
ANS=get(root,0,n,0,p.s+1);
ANS%=mod;
ANS*=(y[p.s])%mod;
ANS%=mod;
cout<<ANS<<endl;
cin>>m;
while(m--){
cin>>u>>pos>>X;
if(u==1){
ad(rot,0,n,pos,n,-log(x[pos]));
x[pos]=X;
ad(rot,0,n,pos,n,log(x[pos]));
add(root,0,n,pos);
} else {
ad(rot,0,n,pos,pos+1,-log(y[pos]));
y[pos]=X;
ad(rot,0,n,pos,pos+1,log(y[pos]));
}
p=rot->D;
ANS=get(root,0,n,0,p.s+1);
ANS%=mod;
ANS*=(y[p.s])%mod;
ANS%=mod;
cout<<ANS<<endl;
}
return 0;
}