| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 649538 | ToroTN | 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<bits/stdc++.h>
using namespace std;
#include "horses.h"
#define ll long long
#define X first
#define Y second
ll n,x[500005],y[500005],md=1e9+7,nw,fight;
ll seg[2000005],val,str,ans,last,mul[2000005],big;
void build(ll tree,ll st,ll ed)
{
ll md=(st+ed)/2;
if(st==ed)
{
seg[tree]=y[ed];
mul[tree]=x[ed];
return;
}
build(2*tree,st,md);
build(2*tree+1,md+1,ed);
seg[tree]=max(seg[2*tree],seg[2*tree+1]);
mul[tree]=1;
if(mul[2*tree]!=0)
{
mul[tree]=(mul[tree]*mul[2*tree]);
mul[tree]%=1000000007;
}
if(mul[2*tree+1]!=0)
{
mul[tree]=(mul[tree]*mul[2*tree+1]);
mul[tree]%=1000000007;
}
}
void update(ll tree,ll st,ll ed,ll idx,ll val)
{
ll md=(st+ed)/2;
if(st==ed)
{
seg[tree]=y[idx];
mul[tree]=x[idx];
return;
}
if(idx<=md)
{
update(2*tree,st,md,idx,val);
}else
{
update(2*tree+1,md+1,ed,idx,val);
}
seg[tree]=max(seg[2*tree],seg[2*tree+1]);
mul[tree]=1;
if(mul[2*tree]!=0)
{
mul[tree]=(mul[tree]*mul[2*tree]);
mul[tree]%=1000000007;
}
if(mul[2*tree+1]!=0)
{
mul[tree]=(mul[tree]*mul[2*tree+1]);
mul[tree]%=1000000007;
}
}
ll query(ll tree,ll st,ll ed,ll l,ll r)
{
ll md=(st+ed)/2;
if(st>r||ed<l)return -1e9;
if(st>=l&&ed<=r)return seg[tree];
return max(query(2*tree,st,md,l,r),query(2*tree+1,md+1,ed,l,r));
}
ll query2(ll tree,ll st,ll ed,ll l,ll r)
{
ll md=(st+ed)/2;
if(st>r||ed<l)return 1;
if(st>=l&&ed<=r)return mul[tree];
return (query2(2*tree,st,md,l,r)*query2(2*tree+1,md+1,ed,l,r))%1000000007;
}
set<ll> s;
stack<pair<ll,ll> > stk;
ll solve()
{
for(auto it=s.begin();it!=s.end();it++)
{
stk.push({*it,query(1,1,n,(*it),n)});
}
nw=n;
str=y[n];
ans=str;
while(!stk.empty())
{
fight=stk.top().X;
val=stk.top().Y;
//printf("%lld %lld\n",fight,val);
stk.pop();
if(str>1e9)
{
str=1e9;
ans*=x[nw];
ans%=md;
}else
{
if(val>str*x[nw])
{
str=val;
ans=val;
}else
{
str*=x[nw];
ans*=x[nw];
ans%=md;
}
}
if(y[fight]>str)
{
str=y[fight];
ans=y[fight];
}
nw=fight;
}
big=query2(1,1,n,1,nw);
//printf("%lld\n",big);
if(str>1e9)
{
str=1e9;
ans*=big;
ans%=md;
return ans;
}else
{
last=seg[1];
if(last>str*big)
{
return last;
}else
{
ans*=big;
ans%=md;
return ans;
}
}
}
ll init(ll N, ll X[], ll Y[]) {
n=N;
for(int i=1;i<=n;i++)
{
x[i]=X[i-1];
y[i]=Y[i-1];
}
build(1,1,n);
for(int i=1;i<n;i++)
{
if(x[i]>1)s.insert(i);
if((int)s.size()>30)
{
if(s.find(*s.begin())!=s.end())
{
s.erase(s.begin());
}
}
}
return solve();
}
ll updateX(ll pos, ll val) {
++pos;
x[pos]=val;
update(1,1,n,pos,val);
if(pos<n)
{
if(x[pos]>1)
{
s.insert(pos);
}else
{
if(s.find(pos)!=s.end())
{
s.erase(pos);
}
}
if(s.size()>30)
{
if(s.find(*s.begin())!=s.end())
{
s.erase(*s.begin());
}
}
}
return solve();
}
ll updateY(ll pos, ll val) {
++pos;
y[pos]=val;
update(1,1,n,pos,val);
return solve();
}