#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 0;
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> g;
vector<ll> p;
int n;
ll solve(){
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 = g[*pt]; // if need be -1 on index
solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
//cout<<g[*pt]<<" "<<*pt<<" "<<last<<" "<<solver[opt - i].second<<"\n";
last = *pt;
temppro *= g[*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;
//cout<<temppro<<" "<<temppro * solver[i].second<<"_ ";
best = max(best, temppro * solver[i].second);
}
best %= mod;
return (best * startproduct)%mod;
//x for growth
// y for prices;
}
int init(int nn, int xx[], int yy[]){
for(int i = 0; i<nn; i++){
g.push_back(xx[i]);
p.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(g[i] > 1){
updatex(0, npo2, 1, i, g[i]);
}
if(g[i] > 1)fasts.insert(i);
}
for(int i = 0; i<n; i++){
updatey(0, npo2, 1, i, p[i]);
}
return solve();
}
int updateX(int pos, int val) {
updatex(0, npo2, 1, pos, val);
if(val == 1){
fasts.erase(pos);
}
else fasts.insert(pos);
g[pos] = val;
return solve();
}
int updateY(int pos, int val) {
updatey(0, npo2, 1, pos, val);
p[pos] = val;
return solve();
}
Compilation message
sorting.cpp:1:10: fatal error: horses.h: No such file or directory
1 | #include "horses.h"
| ^~~~~~~~~~
compilation terminated.
