| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 20198 | HIR180 | Horses (IOI15_horses) | C++98 | 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;
typedef long long ll;
#define mp make_pair
#define fi first
#define sc second
#define pb push_back
#define mod 1000000007
set<pair<int,ll> >S;
typedef pair<pair<int,int>,ll> Q;
int n,m;
ll x[500005],y[500005];
ll seg[(1<<20)];
ll bit[(1<<20)];
void upd(int i,int x){
for(int j=i;j<=n;j+=j&-j){
bit[j] = bit[j]*x%mod;
}
}
ll mul(int i){
ll r = 1;
for(int j=i;j>0;j-=j&-j){
r = r*bit[j]%mod;
}
return r;
}
ll query(int a,int b,int k,int l,int r){
if(r<a || b<l) return 0;
if(a<=l && r<=b) return seg[k];
return max(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2+1,r));
}
void update(int i,int x){
i += (1<<19)-1;
seg[i] = x;
while(i>0){
i = (i-1)/2;
seg[i] = max(seg[i*2+1],seg[i*2+2]);
}
}
ll modpow(ll x,ll n){
ll r = 1;
for(int i=0;i<30;i++){
if(((n>>i)&1)){
r = r*x%mod;
}
x = x*x%mod;
}
return r;
}
int main(){
scanf("%d",&n);
fill(bit,bit+(1<<20),1);
for(int i=0;i<n;i++){
scanf("%lld",&x[i]);
if(x[i] > 1){
S.insert(mp(i,x[i]));
}
upd(i+1,x[i]);
}
if(x[0] == 1) S.insert(mp(0,1));
for(int i=0;i<n;i++){
scanf("%lld",&y[i]);
seg[i+(1<<19)-1] = y[i];
}
for(int i=(1<<19)-2;i>=0;i--) seg[i] = max(seg[i*2+1],seg[i*2+2]);
scanf("%d",&m);
for(int i=0;i<=m;i++){
ll cur = 1;
int pre = n;
set<pair<int,ll> >::iterator it = S.end(); --it;
vector<Q>vq;
for(;;it--){
int L = it->fi;
ll val = it->sc;
vq.pb(mp(mp(L,pre-1),val));
pre = L;
cur *= val;
if(cur > mod || it == S.begin()) break;
}
reverse(vq.begin(),vq.end());
ll lb = mul(pre+1);
ll M = 1; cur = 1;
for(int j=0;j<vq.size();j++){
if(j) cur *= vq[j].sc;
M = max(M,query(vq[j].fi.fi,vq[j].fi.sc,0,0,(1<<19)-1)*cur);
}
M%=mod;
printf("%lld\n",lb*M%mod);
if(i==m) break;
int a,b,c; scanf("%d%d%d",&a,&b,&c);
if(a == 1){
upd(b+1,c*modpow(x[b],mod-2)%mod);
if(b){
if(x[b]==1){
if(c==1);
else{
S.insert(mp(b,c));
}
x[b] = c;
}
else{
set<pair<int,ll> >::iterator it = S.lower_bound(mp(b,x[b]));
assert((*it) == mp(b,x[b]));
S.erase(it);
if(c==1);
else S.insert(mp(b,c));
x[b] = c;
}
}
else{
set<pair<int,ll> >::iterator it = S.lower_bound(mp(b,x[b]));
assert((*it) == mp(b,x[b]));
S.erase(it);
S.insert(mp(b,c));
x[b] = c;
}
}
else{
update(b,c);
}
}
}