| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1276864 | k12_khoi | Horses (IOI15_horses) | C++17 | 0 ms | 0 KiB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pii pair<ll,ll>
#define X first
#define Y second
const int N=5e5+5;
const int mod=1e9+7;
const int limit=1e9;
int n,request,type,x,y,u,v,k;
int a[N],b[N],X[N],Y[N],t[4*N],lazy[4*N],tTwo[4*N];
set <int> se;
set <int> :: iterator it;
int mul(int x,int y)
{
return 1LL*x*y%mod;
}
int luythua(int x,int n)
{
int c=1;
while (n)
{
if (n&1) c=mul(c,x);
x=mul(x,x);
n/=2;
}
return c;
}
void down(int id)
{
if (lazy[id]!=1)
{
lazy[id*2]=mul(lazy[id*2],lazy[id]);
lazy[id*2+1]=mul(lazy[id*2+1],lazy[id]);
tTwo[id*2]=mul(tTwo[id*2],lazy[id]);
tTwo[id*2+1]=mul(tTwo[id*2+1],lazy[id]);
lazy[id]=1;
}
}
void update_range(int id,int l,int r)
{
if (u>r or v<l) return;
if (u<=l and v>=r)
{
tTwo[id]=mul(tTwo[id],k);
lazy[id]=mul(lazy[id],k);
return;
}
down(id);
int m=(l+r)/2;
update_range(id*2,l,m);
update_range(id*2+1,m+1,r);
}
void update_point(int id,int l,int r)
{
if (l==r)
{
t[id]=k;
return;
}
int m=(l+r)/2;
if (u<=m) update_point(id*2,l,m);
else update_point(id*2+1,m+1,r);
t[id]=max(t[id*2],t[id*2+1]);
}
int get_range(int id,int l,int r)
{
if (u>r or v<l) return 0;
if (u<=l and v>=r) return t[id];
int m=(l+r)/2;
return max(get_range(id*2,l,m),get_range(id*2+1,m+1,r));
}
ll get_point(int id,int l,int r)
{
if (l==r)
return tTwo[id];
down(id);
int m=(l+r)/2;
if (u<=m) return get_point(id*2,l,m);
else return get_point(id*2+1,m+1,r);
}
int init(int n,int a[],int b[])
{
for (int i=0;i<n;i++)
{
X[i]=a[i];
Y[i]=b[i];
}
ll cur=1;
function <void(int,int,int)> build = [&] (int id,int l,int r) -> void
{
lazy[id]=1;
tTwo[id]=1;
if (l==r)
{
if (l==0) t[id]=1;
else t[id]=Y[l-1];
if (l) cur=mul(cur,X[l-1]);
tTwo[id]=cur;
return;
}
int m=(l+r)/2;
build(id*2,l,m);
build(id*2+1,m+1,r);
t[id]=max(t[id*2],t[id*2+1]);
};
se.insert(0);
for (int i=0;i<n;i++)
if (X[i]!=1) se.insert(i+1);
build(1,0,n);
it=--se.end();
u=*it;
v=n;
pii ma=make_pair(get_range(1,0,n),1);
ll temp;
int best=*it;
cur=1;
while (it!=se.begin())
{
if (*it) cur*=X[(*it)-1];
if (cur>=limit) break;
it--;
u=*it;
v=n;
temp=get_range(1,0,n);
if (ma.X*cur<temp*ma.Y)
{
best=*it;
cur=1;
ma=make_pair(temp,cur);
}
}
u=best;
temp=get_point(1,0,n);
u=best;
v=n;
return mul(temp,get_range(1,0,n));
}
int updateX(int pos,int val)
{
pos++;
if (X[pos-1]!=val)
{
if (X[pos-1]==1) se.insert(pos);
k=mul(luythua(X[pos-1],mod-2),val);
u=pos;
v=n;
update_range(1,0,n);
X[pos-1]=val;
if (val==1) se.erase(pos);
}
it=--se.end();
u=*it;
v=n;
pii ma=make_pair(get_range(1,0,n),1);
ll temp;
int best=*it;
ll cur=1;
while (it!=se.begin())
{
cur*=X[(*it)-1];
if (cur>=limit) break;
it--;
u=*it;
v=n;
temp=get_range(1,0,n);
if (ma.X*cur<temp*ma.Y)
{
best=*it;
cur=1;
ma=make_pair(temp,cur);
}
}
u=best;
temp=get_point(1,0,n);
u=best;
v=n;
return mul(temp,get_range(1,0,n));
}
int updateY(int pos,int val)
{
pos++;
if (Y[pos-1]!=val)
{
u=pos;
k=val;
update_point(1,0,n);
Y[pos-1]=val;
}
it=--se.end();
u=*it;
v=n;
pii ma=make_pair(get_range(1,0,n),1);
ll temp;
int best=*it;
ll cur=1;
while (it!=se.begin())
{
if (*it) cur*=X[(*it)-1];
if (cur>=limit) break;
it--;
u=*it;
v=n;
temp=get_range(1,0,n);
if (ma.X*cur<temp*ma.Y)
{
best=*it;
cur=1;
ma=make_pair(temp,cur);
}
}
u=best;
temp=get_point(1,0,n);
u=best;
v=n;
return mul(temp,get_range(1,0,n));
}