| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1193284 | vivkostov | Horses (IOI15_horses) | C++20 | 0 ms | 0 KiB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const long long int maxn=1e9+7;
long long int ma[2000005],n,a[500005],b[500005],lamp[2000005];
long long int p[2000005];
vector<long long int>pos;
void build(long long int l,long long int r,long long int h)
{
if(l==r)
{
p[h]=a[l];
ma[h]=b[l];
return;
}
long long 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(long long int l,long long int r,long long int q,long long int h,long long int st)
{
if(l>q||r<q)return;
if(l==r)
{
a[l]=st;
p[h]=a[l];
return;
}
long long 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(long long int l,long long int r,long long int q,long long int h,long long int st)
{
if(l>q||r<q)return;
if(l==r)
{
b[l]=st;
ma[h]=st;
return;
}
long long 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]);
}
long long int get_l(long long int l,long long int r,long long int h,long long int um)
{
if(l==r)
{
if(um*p[h]>1e9)return l+1;
return l;
}
long long int mid=(l+r)/2;
if(lamp[h*2+1]||p[h*2+1]*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(long long int l,long long int r,long long int q,long long int h)
{
if(p[h]==1&&!lamp[h])return;
if(l==r)
{
pos.push_back(l);
return;
}
long long 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(long long int l,long long int r,long long int ql,long long int qr,long long int h)
{
if(l>qr||r<ql)return 1;
if(l>=ql&&r<=qr)return p[h];
long long 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;
}
long long int get_ma(long long int l,long long int r,long long int ql,long long int qr,long long int h)
{
if(l>qr||r<ql)return 0;
if(l>=ql&&r<=qr)return ma[h];
long long 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()
{
long long int to=get_l(1,n,1,1);
get_pos(1,n,to,1);
long long int otg=get_ma(1,n,1,n,1),seg=1,le=1;
pos.push_back(n+1);
for(long long int i=0;i<pos.size()-1;i++)
{
seg*=a[pos[i]];
otg=max(otg,seg*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;
}
long long int init(long long int N, long long int X[], long long int Y[])
{
n=N;
for(long long int i=0;i<n;i++)
{
a[i+1]=X[i];
b[i+1]=Y[i];
}
build(1,n,1);
return resh();
}
long long int updateX(long long int po, long long int val)
{
po++;
updateA(1,n,po,1,val);
return resh();
}
long long int updateY(long long int po, long long int val)
{
po++;
updateB(1,n,po,1,val);
return resh();
}