#include<bits/stdc++.h>
using namespace std;
#define ll long long
const __int128 MOD=1e9+7;
#ifdef __cplusplus
extern "C" {
#endif
int init(int N, int X[], int Y[]);
int updateX(int pos, int val);
int updateY(int pos, int val);
#ifdef __cplusplus
}
#endif
// TODO: global variables can be declared here
struct SEG{
vector<ll>seg,arr;
void init(ll n){
seg.resize(4*n+5),arr.resize(n+5);
}
void build(ll l, ll r, ll id){
if(l==r){
seg[id]=arr[l];
}
else{
ll mid=(l+r)>>1;
build(l,mid,id*2),build(mid+1,r,id*2+1);
seg[id]=max(seg[id*2],seg[id*2+1]);
}
}
void upd(ll ul, ll l, ll r, ll val, ll id){
if(l==r){
seg[id]=val;
}
else{
ll mid=(l+r)>>1;
if(ul<=mid)upd(ul,l,mid,val,id*2);
else upd(ul,mid+1,r,val,id*2+1);
seg[id]=max(seg[id*2],seg[id*2+1]);
}
}
ll qry(ll ql, ll qr, ll l, ll r, ll id){
if(l>qr||r<ql){
return -1e18;
}
if(l>=ql&&r<=qr)return seg[id];
ll mid=(l+r)>>1;
return max(qry(ql,qr,l,mid,id*2),qry(ql,qr,mid+1,r,id*2+1));
}
}st;
struct MULTIPLICATION{
vector<ll>seg,arr;
void init(ll n){
seg.resize(4*n+5),arr.resize(n+5);
}
void build(ll l, ll r, ll id){
if(l==r){
seg[id]=arr[l]%MOD;
}
else{
ll mid=(l+r)>>1;
build(l,mid,id*2),build(mid+1,r,id*2+1);
seg[id]=seg[id*2]*seg[id*2+1];
seg[id]%=MOD;
}
}
void upd(ll ul, ll l, ll r, ll val, ll id){
if(l==r){
seg[id]=val;
seg[id]%=MOD;
}
else{
ll mid=(l+r)>>1;
if(ul<=mid)upd(ul,l,mid,val,id*2);
else upd(ul,mid+1,r,val,id*2+1);
seg[id]=seg[id*2]*seg[id*2+1];
seg[id]%=MOD;
}
}
ll qry(ll ql, ll qr, ll l, ll r, ll id){
if(l>qr||r<ql){
return 1;
}
if(l>=ql&&r<=qr)return seg[id];
ll mid=(l+r)>>1;
return (qry(ql,qr,l,mid,id*2)*qry(ql,qr,mid+1,r,id*2+1)%MOD);
}
}mul;
vector<ll>qry;
set<ll>ms;
vector<ll>x,y;
ll n;
ll func(){
__int128 m=1;
for(ll u: ms){
if(m>MOD){break;}
m*=x[-u];
qry.push_back(-u);
}
ll ans; __int128 maxi=-1e18;
bool ok=0;
if(m<=MOD){
ans=st.qry(1,n,1,n,1);
ok=1;
}
reverse(qry.begin(),qry.end());
m=1;
for(int i=0;i<qry.size();i++){
m*=x[qry[i]];
__int128 mu;
if(i==qry.size()-1)mu=st.qry(qry[i],n,1,n,1);
else mu=st.qry(qry[i],qry[i+1]-1,1,n,1);
if(mu*m>maxi){
maxi=mu*m;
ll store=mu%MOD;
if(!ok){
ans=mul.qry(1,qry[i],1,n,1)*store%MOD;
}
else{
ans=max(ans,mul.qry(1,qry[i],1,n,1)*store);
}
}
}
qry.clear();
return ans%MOD;
}
int init(int N, int X[], int Y[]) {
// TODO: implementation
n=N;
st.init(N);mul.init(n);
x.push_back(0),y.push_back(0);
for(int i=0;i<n;i++){
x.push_back(X[i]);
y.push_back(Y[i]);
}
for(int i=1;i<=n;i++){
st.arr[i]=y[i];
mul.arr[i]=x[i];
}
st.build(1,n,1),mul.build(1,n,1);
for(int i=1;i<=n;i++){
if(x[i]!=1){
ms.insert(-i);
}
}
return func();
}
int updateX(int pos, int val) {
// TODO: implementation
pos++;
if(x[pos]!=1){
ms.erase(-pos);
}
x[pos]=val;
mul.upd(pos,1,n,val,1);
if(x[pos]!=1)ms.insert(-pos);
return func();
}
int updateY(int pos, int val) {
// TODO: implementation
pos++;
y[pos]=val;
st.upd(pos,1,n,val,1);
return func();
}
// int main(){
// ll nn;
// cin>>nn;
// int X[nn+5],Y[nn+5];
// for(int i=0;i<nn;i++){
// cin>>X[i];
// }
// for(int i=0;i<nn;i++){
// cin>>Y[i];
// }
// cout<<init(nn,X,Y)<<'\n';
// ll q;
// cin>>q;
// while(q--){
// ll pos,val;
// cin>>pos>>val;
// cout<<updateY(pos,val)<<'\n';
// }
// }
Compilation message
horses.cpp: In function 'long long int func()':
horses.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i=0;i<qry.size();i++){
| ~^~~~~~~~~~~
horses.cpp:113:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | if(i==qry.size()-1)mu=st.qry(qry[i],n,1,n,1);
| ~^~~~~~~~~~~~~~
horses.cpp:117:24: warning: conversion from '__int128' to 'long long int' may change value [-Wconversion]
117 | ll store=mu%MOD;
| ~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:148:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
148 | return func();
| ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:160:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
160 | return func();
| ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:168:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
168 | return func();
| ~~~~^~
horses.cpp: In function 'long long int func()':
horses.cpp:102:8: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
102 | ll ans; __int128 maxi=-1e18;
| ^~~
/usr/bin/ld: /tmp/ccPiSFNd.o: in function `main':
grader.c:(.text.startup+0xaa): undefined reference to `init(int, int*, int*)'
/usr/bin/ld: grader.c:(.text.startup+0x113): undefined reference to `updateX(int, int)'
/usr/bin/ld: grader.c:(.text.startup+0x16d): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status
