| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 144106 | red1108 | Horses (IOI15_horses) | C++17 | 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<iostream>
#include<stdio.h>
#include<vector>
#include<utility>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define pb push_back
#define enter "\n"
#define space " "
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
const ll INF = 1e18;
const int inf = 1e9;
ll x[500010],y[500010];
ll a[500010],help,b[500010],mod=1000000007;
pli yseg[1050000];
int n, si=1, m, ind=0;
set<int> se;
ll mypow(ll aa, ll bb){
ll ret=1;
while(bb){
if(bb&1) ret = (ret*aa)%mod;
aa = aa*aa%mod;
bb>>=1;
}
return ret;
}
void gangx(int cur, ll t){
if(cur<=ind) help = help*mypow(x[cur],mod-2)%mod*t%mod;
if(x[cur]>1) se.erase(cur);
x[cur]=t;
if(x[cur]>1) se.insert(cur);
}
void gangy(int cur, ll t){
if(cur==ind) help=help*mypow(y[cur],mod-2)%mod*t%mod;
y[cur]=t;
yseg[cur+si-1]=pli(t,cur);
cur+=si-1;
cur>>=1;
while(cur){
yseg[cur] = max(yseg[cur*2],yseg[cur*2+1]);
cur>>=1;
}
}
int getx(bool type, int pos){
if(type){
auto it = se.upper_bound(pos);
if(it==se.end()) return -1;
return *it;
}
auto it = se.lower_bound(pos);
if(it==se.begin()) return -1;
it--;
return *it;
}
pli gety(int cur, int l, int r, int s, int e){
if(l>r||r<s||e<l||s>e) return pli(0,0);
if(s<=l&&r<=e) return yseg[cur];
return max(gety(cur*2,l,(l+r)/2,s,e),gety(cur*2+1,(l+r)/2+1,r,s,e));
}
void go_right(int cur,ll pw){
if(pw*y[cur]>=y[ind]){
help = help*pw%mod*y[cur]%mod*mypow(y[ind],mod-2)%mod;
ind = cur;
pw = 1;
}
if(cur==n) return ;
int nxt = getx(true,cur);
if(nxt==-1) nxt = n;
pli g = gety(1,1,si,cur,nxt-1);
if(y[ind]<g.first*pw){
ind = g.second;
help = help*mypow(y[ind],mod-2)%mod*g.first%mod*pw%mod;
go_right(nxt,1);
}
else go_right(nxt,pw*y[nxt]);
}
void go_left(int cur,ll pw){
if(pw*y[ind]>=1000000000) return ;
if(pw*y[ind]<y[cur]){
help = help*mypow(pw*y[ind]%mod,mod-2)%mod*y[cur]%mod;
ind = cur;
pw = 1;
}
if(cur==1) return;
int nxt = getx(false,cur);
if(nxt==-1) nxt = 1;
pli g = gety(1,1,si,nxt+1,cur);
if(y[ind]*pw<g.first){
help = help*mypow(pw*y[ind]%mod,mod-2)%mod*g.first%mod;
ind = g.second;
go_left(nxt,1);
}
else go_left(nxt,pw*x[cur]);
}
int main(){
//freopen("input.txt", "r", stdin);
fastio;
cin>>n;
while(si<n) si<<=1;
int i;
for(i=1;i<=n;i++){
cin>>x[i];
if(x[i]>1) se.insert(i);
}
for(i=1;i<=n;i++){
cin>>y[i];
yseg[i+si-1]=pli(y[i],i);
}
for(i=si-1;i>=1;i--) yseg[i]=max(yseg[i*2],yseg[i*2+1]);
a[0]=b[0]=1;
for(i=1;i<=n;i++){
a[i]=a[i-1]*x[i];
b[i]=(b[i-1]*x[i])%mod;
if(a[ind]*y[ind]<=a[i]*y[i]){
a[i]=1;
ind = i;
help = b[i]*y[i]%mod;
}
}
cout<<help<<enter;
cin>>m;
while(m--){
ll aa, bb, cc;
cin>>aa>>bb>>cc;
bb++;
if(aa==1) gangx((int)bb,cc);
else gangy((int)bb,cc);
go_right(ind,1);
go_left(ind,1);
cout<<help<<enter;
}
}