#include "horses.h"
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
const int mod=1e9+7, Log=30, maxn=5e5, Log1=19, pot=(1<<Log1);
inline int sum(int a, int b){
if(a+b>=mod){
return a+b-mod;
}
if(a+b<0){
return a+b+mod;
}
return a+b;
}
inline int mul(int a, int b){
return (ll)a*b%mod;
}
inline int pote(int a, int b){
int sol=1;
for(int i=0; i<Log; i++){
if((1<<i)&b){
sol=mul(sol, a);
}
a=mul(a, a);
}
return sol;
}
inline int dij(int a, int b){
return mul(a, pote(b, mod-2));
}
int t[pot*2];
int prop[pot*2];
int a[maxn];
int b[maxn];
void precompute(){
for(int i=1; i<pot*2; i++){
prop[i]=1;
t[i]=1;
}
}
void propagate(int x){
if(prop[x]==1){
return;
}
t[x]=mul(t[x], prop[x]);
if(x<pot){
prop[x*2]=mul(prop[x*2], prop[x]);
prop[x*2+1]=mul(prop[x*2+1], prop[x]);
}
prop[x]=1;
}
void update(int L, int D, int x, int l, int d, int val){
propagate(x);
if(L>=l && D<=d){
t[x]=mul(t[x], val);
// cout << "upd " << x-pot << ' ' << t[x] << endl;
if(x<pot){
prop[x*2]=mul(prop[x*2], val);
prop[x*2+1]=mul(prop[x*2+1], val);
}
return;
}
if((L+D)/2>=l){
update(L, (L+D)/2, x*2, l, d, val);
}
if((L+D)/2+1<=d){
update((L+D)/2+1, D, x*2+1, l, d, val);
}
propagate(x*2);
propagate(x*2+1);
t[x]=max(t[x*2], t[x*2+1]);
}
int init(int n, int x[], int y[]){
precompute();
int val=1;
for(int i=0; i<pot; i++){
if(i<n){
a[i]=x[i];
b[i]=y[i];
val=mul(val, a[i]);
update(0, pot-1, 1, i, i, mul(val, b[i]));
}
else{
update(0, pot-1, 1, i, i, val);
}
}
return t[1];
}
int updateX(int pos, int val){
update(0, pot-1, 1, pos, pot-1, dij(val, a[pos]));
a[pos]=val;
return t[1];
}
int updateY(int pos, int val){
// cout << "val " << b[pos] << ' ' << val << endl;
update(0, pot-1, 1, pos, pos, dij(val, b[pos]));
b[pos]=val;
return t[1];
}
/*
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int x[n], y[n];
for(int i=0; i<n; i++){
cin >> x[i];
}
for(int i=0; i<n; i++){
cin >> y[i];
}
cout << init(n, x, y) << '\n';
int q;
cin >> q;
int a, b, c;
for(int i=0; i<q; i++){
cin >> a >> b >> c;
if(a==1){
cout << updateX(b, c) << '\n';
}
else{
cout << updateY(b, c) << '\n';
}
}
return 0;
}*/
Compilation message
sorting.cpp:1:10: fatal error: horses.h: No such file or directory
1 | #include "horses.h"
| ^~~~~~~~~~
compilation terminated.
