| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 69007 | theknife2001 | Horses (IOI15_horses) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "horses.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
const int N=5e5+55;
long long tree[N*4][2];
long long x[N];
long long y[N];
set < int > st;
int m=1e9+7;
int n;
void build(int l , int r , int node)
{
if(l==r)
{
tree[node][0]=x[l];
tree[node][1]=y[l];
return ;
}
build(l,mid,node*2);
build(mid+1,r,node*2+1);
if(!q)
{
tree[node][q]=tree[node*2][q]*tree[node*2+1][q];
tree[node][q]%=m;
}
else
tree[node]=max(tree[node*2],tree[node*2+1]);
}
void update(int l , int r , int node , int ind , int val , int q)
{
if(l==r&&l==ind)
{
tree[node][q]=val;
return ;
}
if(ind<=mid)
update(l,mid,node*2,ind,val,q);
else
update(mid+1,r,node*2+1,ind,val,q);
if(!q)
{
tree[node][q]=tree[node*2][q]*tree[node*2+1][q];
tree[node][q]%=m;
}
else
tree[node]=max(tree[node*2],tree[node*2+1]);
}
long long query(int l , int r , int node , int x , int y , int q)
{
if(x<=l&&r<=y)
return tree[node][q];
if(l>y||r<x)
return 1;
return (query(l,mid,node*2,x,y,q)*query(mid+1,r,node*2+1,x,y,q))%m;
}
int solve()
{
int i=n-1;
long long ret=0;
long long temp=1;
long long s=1;
bool q=0;
int last=1e9;
for(auto ii:st)
{
i=-ii;
s*=x[i];
if(s>10000000000)
{
i=last;
break;
}
last=i;
}
int bestpos=n-1;
for(upper_bound(st.begin(),st.end(),i)!=st.end())
{
i=-(*upper_bound(st.begin(),st.end(),i));
temp*=x[i];
if(query(0,n-1,1,i,n-1,1)*temp>=ret)
{
ret=y[i]*temp;
bestpos=i;
}
if(ret<0||y[i]*temp<0)
{
assert(0);
}
}
return (query(0,n-1,1,bestpos,n-1,1)*query(0,n-1,1,0,bestpos,0))%m;
}
int init(int N, int X[], int Y[])
{
n=N;
st.insert(0);
for(int i=0;i<N;i++)
{
x[i]=X[i];
if(x[i]!=1)
st.insert(-i);
y[i]=Y[i];
}
build(0,n-1,1);
return solve();
}
int updateX(int pos, int val) {
if(x[pos]==1)
st.insert(-pos);
x[pos]=val;
if(val==1&&pos)
st.erase(-pos);
update(0,n-1,1,pos,val,0);
return solve();
}
int updateY(int pos, int val)
{
y[pos]=val;
update(0,n-1,1,pos,val,1);
return solve();
}