| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 414918 | Bill_00 | Horses (IOI15_horses) | C++14 | 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 <bits/stdc++.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;
int xx[500005],yy[500005];
long long y[500005],x[500005],rightt[500005],leftt[500005];
long long pro[5000000],n,mx[5000000];
set<pair<ll,ll> >s;
void build1(long long id,long long l,long long r){
if(l==r){
mx[id]=y[l];
return;
}
ll m=(l+r)>>1;
build1(id*2,l,m);
build1(id*2+1,m+1,r);
mx[id]=max(mx[id*2],mx[id*2+1]);
}
void build(long long id,long long l,long long r){
if(l==r){
pro[id]=x[l];
return;
}
long long m=(l+r)>>1;
build(id*2,l,m);
build(id*2+1,m+1,r);
pro[id]=pro[id*2]*pro[id*2+1];
if(pro[id]>=MOD) pro[id]%=MOD;
}
long long query(long long id,long long l,long long r,long long L,long long R){
if(R<L) return 1;
if(r<L || R<l) return 1;
if(L<=l && r<=R) return pro[id];
long long m=(l+r)>>1;
return (query(id*2,l,m,L,R)*query(id*2+1,m+1,r,L,R))%MOD;
}
long long query1(ll id,ll l,ll r,ll L,ll R){
if(R<l || r<L) return 0;
if(L<=l && r<=R) return mx[id];
ll m=(l+r)>>1;
return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R));
}
void update(ll id,ll l,ll r,ll d,ll e){
if(l==r){
pro[id]=e;
return;
}
ll m=(l+r)>>1;
if(m>=d) update(id*2,l,m,d,e);
else update(id*2+1,m+1,r,d,e);
pro[id]=pro[id*2]*pro[id*2+1];
if(pro[id]>=MOD) pro[id]%=MOD;
}
void update1(ll id,ll l,ll r,ll d,ll e){
if(l==r){
mx[id]=e;
return;
}
ll m=(l+r)>>1;
if(m>=d) update1(id*2,l,m,d,e);
else update1(id*2+1,m+1,r,d,e);
mx[id]=max(mx[id*2],mx[id*2+1]);
}
int init(int N,int X[],int Y[]){
s.insert({-1,-1});
memset(leftt,-1,sizeof(leftt));
memset(rightt,-1,sizeof(rightt));
n=(long long)N;
for(long long i=0;i<n;i++){
y[i]=(long long)Y[i];
x[i]=(long long)X[i];
}
build(1,0,n-1);
build1(1,0,n-1);
bool flag=0;
long long l;
for(long long i=0;i<n;i++){
if(x[i]==1 && flag==0){
flag=1;
l=i;
}
if(x[i]!=1 && flag==1){
flag=0;
s.insert({l,i-1});
rightt[l]=i-1;
leftt[i-1]=l;
}
}
if(flag==1){
rightt[l]=n-1;
leftt[n-1]=l;
s.insert({l,n-1});
}
long long c=y[n-1];
pair<long double,ll>p={0,-1};
for(ll i=n-1;i>=0;i--){
ll val=y[i];
if(leftt[i]!=-1){
i=leftt[i];
val=query1(1,0,n-1,i,rightt[i]);
}
// cout << (long double)(val)/(long double)(c) << ' ' << i << '\n';
p=max(p,{(long double)(val)/(long double)(c),i});
c*=x[i];
if(c>=1000000000) break;
}
ll ans=query(1,0,n-1,0,p.second);
ll id=p.second,val=y[id];
if(rightt[id]!=-1) val=query1(1,0,n-1,id,rightt[id]);
return (ans*val)%MOD;
}