#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;
int n;
int init(int nn, int xx[], int yy[]){
for(int i = 0; i<n; i++){
x.push_back(xx[i]);
y.push_back(yy[i]);
}
n = nn;
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 solve();
}
int solve(){
int sol = 0;
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;
}
int updateX(int pos, int val) {
return 0;
}
int updateY(int pos, int val) {
return 0;
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:79:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
79 | return queryy(0, npo2, 1, 0, npo2);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~
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;
| ^~~
horses.cpp:102:12: error: 'solve' was not declared in this scope; did you mean 'solver'?
102 | return solve();
| ^~~~~
| solver
horses.cpp:94:8: warning: unused variable 'startproduct' [-Wunused-variable]
94 | ll startproduct = queryx(0, npo2, 1, 0, last);
| ^~~~~~~~~~~~
horses.cpp: In function 'int solve()':
horses.cpp:108:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
108 | return queryy(0, npo2, 1, 0, npo2);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp:118:53: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
118 | solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
| ^~~
horses.cpp:119:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
119 | last = *pt;
| ^~~
horses.cpp:131:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
131 | return (best * startproduct)%mod;
| ~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:106:9: warning: unused variable 'sol' [-Wunused-variable]
106 | int sol = 0;
| ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:139:17: warning: unused parameter 'pos' [-Wunused-parameter]
139 | int updateX(int pos, int val) {
| ~~~~^~~
horses.cpp:139:26: warning: unused parameter 'val' [-Wunused-parameter]
139 | int updateX(int pos, int val) {
| ~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:144:17: warning: unused parameter 'pos' [-Wunused-parameter]
144 | int updateY(int pos, int val) {
| ~~~~^~~
horses.cpp:144:26: warning: unused parameter 'val' [-Wunused-parameter]
144 | int updateY(int pos, int val) {
| ~~~~^~~
