| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1193224 | vivkostov | Horses (IOI15_horses) | C++20 | 0 ms | 0 KiB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e9+7;
int ma[2000005],n,a[500005],b[500005],lamp[2000005];
long long int p[2000005];
vector<int>pos;
void build(int l,int r,int h)
{
if(l==r)
{
p[h]=a[l];
ma[h]=b[l];
return;
}
int mid=(l+r)/2;
build(l,mid,h*2);
build(mid+1,r,h*2+1);
ma[h]=max(ma[h*2],ma[h*2+1]);
p[h]=p[h*2]*p[h*2+1];
if(p[h]>=maxn)
{
lamp[h]=1;
p[h]=p[h]%maxn;
}
else lamp[h]=max(lamp[h*2],lamp[h*2+1]);
}
void updateA(int l,int r,int q,int h,int st)
{
if(l>q||r<q)return;
if(l==r)
{
a[l]=st;
p[h]=a[l];
return;
}
int mid=(l+r)/2;
updateA(l,mid,q,h*2,st);
updateA(mid+1,r,q,h*2+1,st);
p[h]=p[h*2]*p[h*2+1];
if(p[h]>=maxn)
{
lamp[h]=1;
p[h]=p[h]%maxn;
}
else lamp[h]=max(lamp[h*2],lamp[h*2+1]);
}
void updateB(int l,int r,int q,int h,int st)
{
if(l>q||r<q)return;
if(l==r)
{
b[l]=st;
ma[h]=st;
return;
}
int mid=(l+r)/2;
updateB(l,mid,q,h*2,st);
updateB(mid+1,r,q,h*2+1,st);
ma[h]=max(ma[h*2],ma[h*2+1]);
}
void check(int l,int r,int h)
{
cout<<l<<" "<<r<<" "<<p[h]<<" "<<" "<<ma[h]<<endl;
if(l==r)return;
int mid=(l+r)/2;
check(l,mid,h*2);
check(mid+1,r,h*2+1);
}
int get_l(int l,int r,int h,long long int um)
{
if(l==r)
{
if(um*p[h]>1e9)return l++;
return l;
}
int mid=(l+r)/2;
if(lamp[h*2+1]||p[h*2]*um>1e9)return get_l(mid+1,r,h*2+1,um);
else return get_l(l,mid,h*2,um*p[h*2+1]);
}
void get_pos(int l,int r,int q,int h)
{
if(l==r)
{
if(p[h]!=1)pos.push_back(l);
return;
}
int mid=(l+r)/2;
if(mid>=q)get_pos(l,mid,q,h*2);
get_pos(mid+1,r,q,h*2+1);
}
long long int get_st(int l,int r,int ql,int qr,int h)
{
if(l>qr||r<ql)return 0;
if(l>=ql&&r<=qr)return p[h];
int mid=(l+r)/2;
return (get_st(l,mid,ql,qr,h*2)*get_st(mid+1,r,ql,qr,h*2+1))%maxn;
}
int get_ma(int l,int r,int ql,int qr,int h)
{
if(l>qr||r<ql)return 0;
if(l>=ql&&r<=qr)return ma[h];
int mid=(l+r)/2;
return max(get_ma(l,mid,ql,qr,h*2),get_ma(mid+1,r,ql,qr,h*2+1));
}
long long int resh()
{
int to=1;//get_l(1,n,1,1);
get_pos(1,n,1,to);
long long int otg=0,seg=1,le=1,ma;
pos.push_back(n+1);
for(int i=0;i<pos.size()-1;i++)
{
seg*=a[pos[i]];
ma=0;
for(int j=pos[i];j<pos[i+1];j++)
{
ma=max(ma,a[j]);
}
otg=max(otg,seg*ma)//*get_ma(1,n,pos[i],pos[i+1]-1,1));
}
pos.clear();
if(to!=1)le=get_st(1,n,1,to-1,1);
return ((otg%maxn)*le)%maxn;
}
int init(int N, int X[], int Y[])
{
n=N;
for(int i=0;i<n;i++)
{
a[i+1]=X[i];
b[i+1]=Y[i];
}
build(1,n,1);
return resh();
}
int updateX(int po, int val)
{
po++;
updateA(1,n,po,1,val);
return resh();
}
int updateY(int po, int val)
{
po++;
updateB(1,n,po,1,val);
return resh();
}