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 <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <set>
using namespace std;
long long XX[500005];
long long YY[500005];
long long how[500005]={0};
long long MOD=1e9+7;
long long N;
set < long long > all;
struct A
{
long long l,r;
long long con;
long long big;
A* nxl,*nxr;
void build(long long ll,long long rr)
{
l=ll;
r=rr;
if(ll+1==rr)
{
con=XX[ll];
big=YY[ll];
return;
}
nxl=(A*) malloc(sizeof(A));
nxr=(A*) malloc(sizeof(A));
nxl->build(ll,(ll+rr)/2);
nxr->build((ll+rr)/2,rr);
con=nxl->con*nxr->con%MOD;
big=max(nxl->big,nxr->big);
}
void cha(long long where,long long tt)
{
if(l==where&&r==where+1)
{
con=tt;
return;
}
if(where<(l+r)/2) nxl->cha(where,tt);
else nxr->cha(where,tt);
con=nxl->con*nxr->con%MOD;
}
long long Find(long long ll,long long rr)
{
if(ll==l&&rr==r) return con;
if(rr<=(l+r)/2) return nxl->Find(ll,rr);
if(ll>=(l+r)/2) return nxr->Find(ll,rr);
return nxl->Find(ll,(l+r)/2)*nxr->Find((l+r)/2,rr)%MOD;
}
void cha2(long long where,long long tt)
{
if(l==where&&r==where+1)
{
big=tt;
return;
}
if(where<(l+r)/2) nxl->cha2(where,tt);
else nxr->cha2(where,tt);
big=max(nxl->big,nxr->big);
}
long long Find2(long long ll,long long rr)
{
if(ll==l&&rr==r) return big;
if(rr<=(l+r)/2) return nxl->Find2(ll,rr);
if(ll>=(l+r)/2) return nxr->Find2(ll,rr);
return max(nxl->Find2(ll,(l+r)/2),nxr->Find2((l+r)/2,rr));
}
};
A* root;
int init(int N, int X[], int Y[])
{
all.insert(-1);
long long ans=0,t=1,i,now=0,xx,tt,aa;
::N=N;
for(i=0;i<N;i++)
{
XX[i]=(long long) X[i];
YY[i]=(long long) Y[i];
if(XX[i]>=2) all.insert(i);
}
root=(A*)malloc(sizeof(A));
root->build(0,N);
now=YY[N-1];
t=YY[N-1];
now*=XX[N-1];
ans=t*root->Find(0,N)%MOD;
t*=XX[N-1];
xx=N-1;
while(now<=1000000000)
{
tt=*prev(all.lower_bound(xx));
if(tt==-1)
{
if(xx)
{
aa=root->Find2(0,xx);
if(aa>now)
{
now=aa;
t=aa;
}
ans=now;
}
break;
}
else
{
aa=root->Find2(tt,xx);
if(aa>now)
{
now=aa;
t=aa;
}
//printf("%lld %lld %lld %lld \n",t,now,tt,xx);
ans=t*root->Find(0,tt+1)%MOD;
if(now<1000000000) now*=XX[tt];
else break;
t*=XX[tt];
t%=MOD;
xx=tt;
}
}
return (int) ans;
}
int updateX(int pos, int val)
{
long long ans=0,t=1,i,now=0,xx,tt,aa;
if(XX[pos]>=2) all.erase(pos);
XX[pos]=(long long) val;
if(XX[pos]>=2) all.insert(pos);
root->cha(pos,val);
now=YY[N-1];
t=YY[N-1];
now*=XX[N-1];
ans=t*root->Find(0,N)%MOD;
t*=XX[N-1];
xx=N-1;
while(now<=1000000000)
{
tt=*prev(all.lower_bound(xx));
if(tt==-1)
{
if(xx)
{
aa=root->Find2(0,xx);
if(aa>now)
{
now=aa;
t=aa;
}
ans=now;
}
break;
}
else
{
aa=root->Find2(tt,xx);
if(aa>now)
{
now=aa;
t=aa;
}
//printf("%lld %lld %lld %lld \n",t,now,tt,xx);
ans=t*root->Find(0,tt+1)%MOD;
if(now<1000000000) now*=XX[tt];
else break;
t*=XX[tt];
t%=MOD;
xx=tt;
}
}
return (int) ans;
}
int updateY(int pos, int val)
{
long long ans=0,t=1,i,now=0,xx,tt,aa;
YY[pos]=(long long) val;
root->cha2(pos,val);
now=YY[N-1];
t=YY[N-1];
now*=XX[N-1];
ans=t*root->Find(0,N)%MOD;
t*=XX[N-1];
xx=N-1;
while(now<=1000000000)
{
tt=*prev(all.lower_bound(xx));
if(tt==-1)
{
if(xx)
{
aa=root->Find2(0,xx);
if(aa>now)
{
now=aa;
t=aa;
}
ans=now;
}
break;
}
else
{
aa=root->Find2(tt,xx);
if(aa>now)
{
now=aa;
t=aa;
}
//printf("%lld %lld %lld %lld \n",t,now,tt,xx);
ans=t*root->Find(0,tt+1)%MOD;
if(now<1000000000) now*=XX[tt];
else break;
t*=XX[tt];
t%=MOD;
xx=tt;
}
}
return (int) ans;
}
Compilation message (stderr)
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:74:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
74 | int init(int N, int X[], int Y[])
| ~~~~^
horses.cpp:11:11: note: shadowed declaration is here
11 | long long N;
| ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:135:25: warning: unused variable 'i' [-Wunused-variable]
135 | long long ans=0,t=1,i,now=0,xx,tt,aa;
| ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:188:25: warning: unused variable 'i' [-Wunused-variable]
188 | long long ans=0,t=1,i,now=0,xx,tt,aa;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |