| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 349049 | qwerasdfzxcl | 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>
typedef long long ll;
using namespace std;
struct l3{
ll r;
bool inf;
l3(){}
l3(ll _r, bool _inf){r=_r, inf=_inf;}
};
struct node{
int idx;
ll pre, all;
l3 pl, sl, al;
node(){}
node(int _idx, ll _pre, ll _all, l3 _pl, l3 _sl, l3 _al){
idx=_idx, pre=_pre, all=_all, pl=_pl, sl=_sl, al=_al;
}
};
node tree[2002000];
ll x[500500], y[500500], mod=1e9+7;
int n;
ll pw(ll a, ll b){
if (!b) return 1;
ll tmp=pw(a, b/2);
tmp=(tmp*tmp)%mod;
if (b&1) tmp=(tmp*a)%mod;
return tmp;
}
ll rev(ll a){
return pw(a, mod-2);
}
l3 mul(l3 a, l3 b){
l3 ret;
if (a.inf || b.inf) return l3(0, 1);
if (a.r*b.r>=mod) return l3(0, 1);
ret=l3(a.r*b.r, 0);
return ret;
}
node combine(node &a, node &b){
if (a.idx==-2) return b;
if (b.idx==-2) return a;
node ret;
ret.all=(a.all*b.all)%mod;
ret.al=mul(a.al, b.al);
l3 chk=mul(mul(a.sl, b.pl), l3(y[b.idx], 0));
if (chk.inf || chk.r>=y[a.idx]){
ret.idx=b.idx;
ret.pre=(a.all*b.pre)%mod;
ret.pl=mul(a.al, b.pl);
ret.sl=b.sl;
return ret;
}
ret.idx=a.idx;
ret.pre=a.pre;
ret.pl=a.pl;
ret.sl=mul(a.sl, b.al);
return ret;
}
void build(){
for (int i=n-1;i>0;i--) tree[i]=combine(tree[i<<1], tree[i<<1|1]);
}
void update(int i, node val){
for (tree[i += n]=val;i >>= 1;) tree[i]=combine(tree[i<<1], tree[i<<1|1]);
}
node query(int l, int r){
node resl=node(-2, 1, 1, l3(1, 0), l3(1, 0), l3(1, 0)), resr=node(-2, 1, 1, l3(1, 0), l3(1, 0), l3(1, 0));
for (l += n, r += n;l<r;l>>=1, r>>=1){
if (l&1) resl=combine(resl, tree[l++]);
if (r&1) resr=combine(tree[--r], resr);
}
return combine(resl, resr);
}
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int m;
y[0]=1;
cin >> n;
for (int i=1;i<=n;i++) cin >> x[i];
for (int i=1;i<=n;i++) cin >> y[i];
for (int i=0;i<n;i++){
ll tmp=(((x[i+1]*y[i+1])%mod)*rev(y[i]))%mod;
tree[n+i].all=tmp;
tree[n+i].al=l3(x[i+1], 0);
if (x[i+1]*y[i+1]>=y[i]){
tree[n+i].idx=i+1;
tree[n+i].pre=tmp;
tree[n+i].pl=l3(x[i+1], 0);
tree[n+i].sl=l3(1, 0);
}
else{
tree[n+i].idx=i;
tree[n+i].pre=1;
tree[n+i].pl=l3(1, 0);
tree[n+i].sl=l3(x[i+1], 0);
}
}
build();
cout << query(0, n).pre << '\n';
cin >> m;
while(m--){
int tp, pos;
ll val0;
cin >> tp >> pos >> val0;
if (tp==1){
node val=tree[pos+n];
ll tmp=(rev(x[pos+1])*val0)%mod;
val.all=(val.all*tmp)%mod;
val.al=l3(val0, 0);
if (val.idx!=pos+1) val.sl=l3(val0, 0);
else{
val.pre=val.all;
val.pl=l3(val0, 0);
}
x[pos+1]=val0;
update(pos, val);
cout << query(0, n).pre << '\n';
}
else{
node val1=tree[pos+n], val2=tree[pos+1+n];
ll tmp1=(rev(y[pos+1])*val0)%mod;
ll tmp2=rev(tmp1);
val1.all=(val1.all*tmp1);
if (val1.idx==pos+1) val1.pre=val1.all;
y[pos+1]=val0;
update(pos, val1);
if(pos!=n-1){
val2.all=(val2.all*tmp2)%mod;
if (val2.idx==pos+2) val2.pre=val2.all;
update(pos+1, val2);
}
cout << query(0, n).pre << '\n';
}
}
return 0;
}