#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "horse.h"
using namespace std;
const ll mod=round(1e9)+7;
set <int> s;
struct pt { ll x,y; };
pt operator + (pt a,pt b) { return { a.x*b.x%mod,max(a.y,b.y) }; }
int x[100005],y[100005],n,i,u,q,type,pos,val;
struct Interval_Tree
{
pt st[4*500005];
void update(int id,int l,int r,int u)
{
if(l==r) { st[id]={ x[i],y[i] }; return ; }
int mid=(l+r)>>1;
if(u<=mid) update(id*2,l,mid,u);
else update(id*2+1,mid+1,r,u);
st[id]=st[id*2]+st[id*2+1];
}
pt get(int id,int l,int r,int u,int v)
{
if(u>r || v<l) return { 1,0 };
if(u<=l && r<=v) return st[id];
int mid=(l+r)>>1;
return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
}
} IT;
ll Cal()
{
set <int>::iterator it=s.end();
ll ma=0,res=0,last=n+1;
while(it!=s.begin())
{
it--;
int u=*it;
ll k=IT.get(1,1,n,u,last-1).y;
if(ma<k)
{
ma=k;
res=IT.get(1,1,n,1,u).x*ma%mod;
}
ma=ma*x[u];
if(ma>round(1e9)) break;
last=u;
}
return res;
}
int init(int n,int _x[],int _y[])
{
s.insert(0);
for(i=n;i>=1;i--)
{
x[i]=_x[i-1],y[i]=_y[i-1];
if(x[i]>=2) s.insert(i);
IT.update(1,1,n,i);
}
x[0]=1;
return Cal();
}
int updateX(int u,int k)
{
u++;
s.erase(u);
x[u]=k;
if(x[u]>=2) s.insert(u);
IT.update(1,1,n,u);
return Cal();
}
int updateY(int u,int k)
{
u++;
y[u]=k;
IT.update(1,1,n,u);
return Cal();
}
/*
int main()
{
freopen("horse.inp","r",stdin);
freopen("horse.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(i=0;i<n;i++) cin>>x[i];
for(i=0;i<n;i++) cin>>y[i];
cout<<init(n,x,y)<<'\n';
cin>>q;
while(q--)
{
cin>>type>>pos>>val;
if(type==1) cout<<updateX(pos,val)<<'\n';
else cout<<updateY(pos,val)<<'\n';
}
}
*/
Compilation message
horses.cpp:16:10: fatal error: horse.h: No such file or directory
16 | #include "horse.h"
| ^~~~~~~~~
compilation terminated.
