#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
int n=0;
vector<int> x;
vector<int> y;
const long long MOD=1e9+7;
int MUL(long long a, long long b){
return (a*b)%MOD;
}
struct maxsegtree{
vector<int> tree;
void init(){
tree.assign(n*4, 0);
}
int update(int l, int r, int v, int x, int val){
if(x<l || r<=x) return tree[v];
if(l+1==r){
return tree[v]=val;
}
int m=l+(r-l)/2;
return tree[v]=max(update(l, m, v*2+1, x, val), update(m, r, v*2+2, x, val));
}
int query(int l, int r, int v, int ql, int qr){
if(qr<=l || r<=ql) return 1;
if(ql<=l && r<=qr){
return tree[v];
}
int m=l+(r-l)/2;
return max(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
}
};
maxsegtree maxseg;
struct productsegtree{
vector<int> tree;
void init(){
tree.assign(n*4, 1);
}
int update(int l, int r, int v, int x, int val){
if(x<l || r<=x) return tree[v];
if(l+1==r){
return tree[v]=val;
}
int m=l+(r-l)/2;
return tree[v] = MUL(update(l, m, v*2+1, x, val), update(m, r, v*2+2, x, val));
}
int query(int l, int r, int v, int ql, int qr){
if(qr<=l || r<=ql) return 1;
if(ql<=l && r<=qr){
return tree[v];
}
int m=l+(r-l)/2;
return MUL(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
}
};
productsegtree pseg;
set<int> notone;
bool bigger(pair<long long, long long> a, pair<long long, long long> b){
return a.first*b.second > a.second*b.first;
}
int solve(){
auto it=notone.end();
long long product=1;
pair<int, long long> best={1, 1};
int ind=n-1;
bool mod=false;
while(!mod && it!=notone.begin()){
it=prev(it);
int pos=*it;
int yfac=maxseg.query(0, n, 0, pos, n);
if(bigger({yfac, product}, best)){
best={yfac, product};
ind=pos;
}
product*=x[pos];
if(product>MOD){
product%=MOD;
mod=true;
}
}
//check first one
int yfac=maxseg.query(0, n, 0, 0, n);
product=pseg.query(0, n, 0, 1, n);
if(!mod && bigger({yfac, product}, best)){
best={yfac, product};
ind = 0;
}
int yfac=maxseg.query(0, n, 0, ind, n);
int xfac=pseg.query(0, n, 0, 0, ind+1);
int ans=MUL(xfac, yfac);
return ans;
}
int init(int N, int X[], int Y[]) {
n=N;
x.assign(n, 0);
for(int i=0; i<n; i++){
x[i]=X[i];
}
y.assign(n, 0);
for(int i=0; i<n; i++){
y[i]=Y[i];
}
maxseg.init();
for(int i=0; i<n; i++){
maxseg.update(0, n, 0, i, y[i]);
}
pseg.init();
for(int i=0; i<n; i++){
pseg.update(0, n, 0, i, x[i]);
}
for(int i=0; i<n; i++){
if(x[i]!=1){
notone.insert(i);
}
}
return solve();
}
int updateX(int pos, int val) {
if(x[pos]==1 && val!=1){
notone.insert(pos);
}
if(x[pos]!=1 && val==1){
notone.erase(pos);
}
x[pos]=val;
pseg.update(0, n, 0, pos, val);
return solve();
}
int updateY(int pos, int val) {
y[pos]=val;
maxseg.update(0, n, 0, pos, val);
return solve();
}
Compilation message
horses.cpp: In function 'int MUL(long long int, long long int)':
horses.cpp:12:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
12 | return (a*b)%MOD;
| ~~~~~^~~~
horses.cpp: In member function 'int maxsegtree::update(int, int, int, int, int)':
horses.cpp:22:41: warning: declaration of 'x' shadows a global declaration [-Wshadow]
22 | int update(int l, int r, int v, int x, int val){
| ~~~~^
horses.cpp:6:13: note: shadowed declaration is here
6 | vector<int> x;
| ^
horses.cpp: In member function 'int productsegtree::update(int, int, int, int, int)':
horses.cpp:49:41: warning: declaration of 'x' shadows a global declaration [-Wshadow]
49 | int update(int l, int r, int v, int x, int val){
| ~~~~^
horses.cpp:6:13: note: shadowed declaration is here
6 | vector<int> x;
| ^
horses.cpp: In function 'int solve()':
horses.cpp:112:9: error: redeclaration of 'int yfac'
112 | int yfac=maxseg.query(0, n, 0, ind, n);
| ^~~~
horses.cpp:103:9: note: 'int yfac' previously declared here
103 | int yfac=maxseg.query(0, n, 0, 0, n);
| ^~~~
