| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1191004 | simona1230 | 말 (IOI15_horses) | C++20 | 0 ms | 0 KiB |
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
//static FILE *_inputFile, *_outputFile;
const int mod=1e9+7;
const int maxn=5*1e5+5;
long long n,x[maxn],y[maxn];
long long maxx[4*maxn],prod[4*maxn];
int qmax(int i,int l,int r,int ql,int qr)
{
if(ql>qr)return 0;
if(ql<=l&&r<=qr)return maxx[i];
int m=(l+r)/2;
return max(qmax(i*2,l,m,ql,min(qr,m)),qmax(i*2+1,m+1,r,max(m+1,ql),qr));
}
long long qprod(int i,int l,int r,int ql,int qr)
{
if(ql>qr)return 1;
if(ql<=l&&r<=qr)return prod[i];
int m=(l+r)/2;
return (qprod(i*2,l,m,ql,min(qr,m))*qprod(i*2+1,m+1,r,max(m+1,ql),qr))%mod;
}
set<int> s;
long long answer()
{
if(n==1)return (x[0]*y[0])%mod;
if(s.size()==0)return maxx[1];
//for(auto it=s.begin();it!=s.end();it++)
// cout<<*it<<endl;
auto it=s.end();
long long curr=0,id=0,hh=0;
while(it!=s.begin())
{
int nxt=n-1;
if(it!=s.end())nxt=*it-1;
it--;
int i=*it;
int h=qmax(1,0,n-1,i,nxt);
//fprintf(_outputFile,"%d ",nxt);
//cout<<"+ "<<h<<endl;
if(curr<h)curr=h,id=i,hh=h;
curr*=x[i];
if(curr>1e9)break;
}
//cout<<id<<endl;
return (qprod(1,0,n-1,0,id)*hh)%mod;
}
void umaxx(int i,int l,int r,int id,int vl)
{
if(l==r)
{
maxx[i]=vl;
return;
}
int m=(l+r)/2;
if(id<=m)umaxx(i*2,l,m,id,vl);
else umaxx(i*2+1,m+1,r,id,vl);
maxx[i]=max(maxx[i*2],maxx[i*2+1]);
}
void uprod(int i,int l,int r,int id,int vl)
{
if(l==r)
{
prod[i]=vl;
return;
}
int m=(l+r)/2;
if(id<=m)uprod(i*2,l,m,id,vl);
else uprod(i*2+1,m+1,r,id,vl);
prod[i]=(prod[i*2]*prod[i*2+1])%mod;
}
void build(int i,int l,int r)
{
if(l==r)
{
maxx[i]=y[l];
prod[i]=x[l];
return;
}
int m=(l+r)/2;
build(i*2,l,m);
build(i*2+1,m+1,r);
maxx[i]=max(maxx[i*2],maxx[i*2+1]);
prod[i]=(prod[i*2]*prod[i*2+1])%mod;
}
int init(int N, int X[], int Y[])
{
n=N;
for(int i=0;i<N;i++)
x[i]=X[i],y[i]=Y[i];
build(1,0,n-1);
for(int i=0;i<N;i++)
if(x[i]!=1)s.insert(i);
s.insert(0);
return answer();
}
int updateX(int pos, int val)
{
x[pos]=val;
if(val==1&&pos)s.erase(pos);
else s.insert(pos);
uprod(1,0,n-1,pos,val);
return answer();
}
int updateY(int pos, int val)
{
y[pos]=val;
umaxx(1,0,n-1,pos,val);
return answer();
}
long long answer1()
{
if(n==1)return x[0]*y[0]%mod;
long long curr=0,id=0;
for(int i=n-1;i>=0;i--)
{
if(curr<y[i])
id=i,curr=x[i]*y[i];
else curr*=x[i];
if(curr>1e9)break;
///fprintf(_outputFile,"%d ",curr);
}
long long ans=1;
for(int i=0;i<=id;i++)
{
ans*=x[i];
ans%=mod;
}
return ans*y[id]%mod;
}
int init1(int N, int X[], int Y[])
{
n=N;
for(int i=0;i<N;i++)
x[i]=X[i],y[i]=Y[i];
return answer();
}
int updateX1(int pos, int val)
{
x[pos]=val;
return answer();
}
int updateY1(int pos, int val)
{
y[pos]=val;
return answer();
}
int nn,xx[maxn],yy[maxn],qq;
int main()
{
cin>>nn;
for(int i=0;i<nn;i++)
cin>>xx[i];
for(int i=0;i<nn;i++)
cin>>yy[i];
cout<<init(nn,xx,yy)<<endl;
cin>>qq;
for(int i=0;i<qq;i++)
{
int t,id,vl;
cin>>t>>id>>vl;
if(t==1)cout<<updateX(id,vl)<<endl;
else cout<<updateY(id,vl)<<endl;
}
return 0;
}
/*
3
2 1 3
3 4 1
1
2 1 2
*/