#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define ll long long
#define fastOI ios_base::sync_with_stdio(false); cin.tie(nullptr);
auto cmp = [](int a, int b){return a > b;};
auto cmp1 = [](pair<ll,ll> a, pair<ll,ll> b){return a.second < b.second;};
ll mod = 1000000007;
vector<ll> segtreex;
vector<ll> segtreey;
void updatex(int l, int r, int pos, int ind, ll x){
int m = l + (r - l)/2;
if(ind < l || ind >= r)return;
if(l == ind && l + 1 == r){
segtreex[pos] = x;
return;
}
updatex(l, m, pos*2, ind, x);
updatex(m, r, pos*2 + 1, ind, x);
segtreex[pos] = (segtreex[pos*2] * segtreex[pos*2 + 1])%mod;
return;
}
ll queryx(int l, int r, int pos, int ql, int qr){
if( ql >= l && qr <= r)return segtreex[pos];
if( qr <= l || ql >= r)return 1;
int m = l + (r-l)/2;
return (queryx(l, m, pos * 2, ql, qr) * queryx(m, r, pos*2 + 1, ql, qr))%mod;
}
void updatey(int l, int r, int pos, int ind, ll x){
int m = l + (r - l)/2;
if(ind < l || ind >= r)return;
if(l == ind && l + 1 == r){
segtreey[pos] = x;
return;
}
updatey(l, m, pos*2, ind, x);
updatey(m, r, pos*2 + 1, ind, x);
segtreey[pos] = max(segtreey[pos*2], segtreey[pos*2 + 1]);
return;
}
ll queryy(int l, int r, int pos, int ql, int qr){
if( ql >= l && qr <= r)return segtreey[pos];
if( qr <= l || ql >= r)return 1;
int m = l + (r-l)/2;
return max(queryy(l, m, pos * 2, ql, qr), queryy(m, r, pos*2 + 1, ql, qr));
}
set<ll> fasts;
int npo2;
vector<ll> x;
vector<ll> y;
ll init(int n, int xx[], int yy[]){
for(int i = 0; i<n; i++){
x.push_back(xx[i]);
y.push_back(yy[i]);
}
ll sol = 0;
npo2 = __lg(n-1) + 1;
npo2 = (1<<npo2);
segtreex.resize(npo2 * 2, 1);
segtreey.resize(npo2 * 2, 0);
for(int i = 0; i<n; i++){
if(x[i] > 1)updatex(0, npo2, 1, i, x[i]);
if(x[i] > 1)fasts.insert(i);
}
for(int i = 0; i<n; i++){
updatey(0, npo2, 1, i, y[i]);
}
if(fasts.empty()){
return queryy(0, npo2, 1, 0, npo2);
}
vector<pair<ll,ll>> solver(30,{1, 1});
set<ll>::iterator pt = fasts.end();
int opt = (min(30, int(fasts.size())));
int last = n;
ll temppro = 1;
for(int i = 0 ;i < opt; i++){
pt--;
solver[opt - i].first = x[*pt];
solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
last = *pt;
temppro *= x[*pt];
if(temppro >= mod)break;
}
ll startproduct = queryx(0, npo2, 1, 0, last);
temppro = 1;
ll best = 1;
for(int i = 0; i < opt; i++){
temppro *= solver[i].first;
best = max(best, temppro * solver[i].second);
}
best %= mod;
return (best * startproduct)%mod;
//x for growth
// y for prices;
return sol;
}
/*
int main(){
int a[] = {2, 1, 3};
int b[] = {3, 4, 1};
cout<<init(3, a , b);
}
*/
Compilation message
horses.cpp:60:4: error: ambiguating new declaration of 'long long int init(int, int*, int*)'
60 | ll init(int n, int xx[], int yy[]){
| ^~~~
In file included from horses.cpp:1:
horses.h:4:5: note: old declaration 'int init(int, int*, int*)'
4 | int init(int N, int X[], int Y[]);
| ^~~~
horses.cpp: In function 'long long int init(int, int*, int*)':
horses.cpp:89:53: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
89 | solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
| ^~~
horses.cpp:90:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
90 | last = *pt;
| ^~~
