| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 99628 | DiegoGarcia | 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>
#define optimiza_io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define ft first
#define sd second
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const ll maxn = 500005, mod = 1e9+7ll;
ll n;
ll x[maxn],y[maxn];
ll stprod[4*maxn]; //-1 es overflow, sino, es normal
ll stmax[4*maxn];
ll stmodded[4*maxn];
void build1( ll nodo, ll ini, ll fin )
{
if( ini == fin )
{
stprod[nodo] = x[ini];
stmodded[nodo] = x[ini]%mod;
return;
}
ll md = (ini+fin)/2;
build1( 2*nodo+1, ini, md );
build1( 2*nodo+2, md+1, fin );
if( stprod[2*nodo+1] == -1 || stprod[2*nodo+2] == -1 )
stprod[nodo] = -1;
else if( ((ld)stprod[2*nodo+1]) > (((ld)LLONG_MAX) / ((ld)stprod[2*nodo+2])) ) //habrá overflow
stprod[nodo] = -1;
else
stprod[nodo] = stprod[2*nodo+1] * stprod[2*nodo+2];
stmodded[nodo] = (stmodded[2*nodo+1] * stmodded[2*nodo+2])%mod;
return;
}
ll getprod( ll nodo, ll ini, ll fin, ll sq, ll eq ) // -1
{
if( ini > eq || fin < sq ){
return 1ll;
}
if( ini >= sq && fin <= eq )
{
stmodded[nodo] = x[ini];
if( stprod[nodo] == -1 )
return -1;
return stprod[nodo];
}
ll md = (ini+fin)/2;
ll izq = getprod( 2*nodo+1, ini, md, sq, eq );
ll der = getprod( 2*nodo+2, md+1, fin, sq, eq );
if( izq == -1 || der == -1 ) return -1;
if( ((ld)izq) > (((ld)LLONG_MAX) / ((ld)der)) ) return -1;
return izq*der;
}
ll getprod2( ll nodo, ll ini, ll fin, ll sq, ll eq )
{
if( ini > eq || fin < sq ) return 1ll;
if( ini >= sq && fin <= eq ) return stmodded[nodo];
ll md = (ini+fin)/2;
return ( getprod( 2*nodo+1, ini, md, sq, eq ) * getprod( 2*nodo+2, md+1, fin, sq, eq ) )%mod;
}
void upd_max( ll nodo )
{
ll right_prod = getprod( 0, 0, n-1, stmax[2*nodo+1] + 1, stmax[2*nodo+2] );
if( ((ld)right_prod) > (((ld)LLONG_MAX) / ((ld)y[stmax[2*nodo+2]]) ) )
right_prod = -1;
else
right_prod *= y[stmax[2*nodo+2]];
if(right_prod == -1 || right_prod > y[stmax[2*nodo+1]] )
stmax[nodo] = stmax[2*nodo+2];
else
stmax[nodo] = stmax[2*nodo+1];
return;
}
void build2( ll nodo, ll ini, ll fin )
{
if( ini == fin )
{
stmax[nodo] = ini;
return;
}
ll md = (ini+fin)/2;
build2( 2*nodo+1, ini, md );
build2( 2*nodo+2, md+1, fin );
upd_max(nodo);
return;
}
void upd_y( ll nodo, ll ini, ll fin, ll p )
{
if( ini > p || fin < p ) return;
if( ini == fin ){
return;
}
ll md = (ini+fin)/2;
if( p <= md )
upd_y( 2*nodo+1, ini, md, p );
else
upd_y( 2*nodo+2, md+1, fin, p );
upd_max( nodo );
return;
}
void upd_prod( ll nodo, ll ini, ll fin, ll p )
{
if( ini > p || fin < p ) return;
if( ini == fin )
{
stprod[nodo] = x[ini];
stmodded[nodo] = x[ini]%mod;
return;
}
ll md = (ini+fin)/2;
if( p <= md )
upd_prod( 2*nodo+1, ini, md, p );
else
upd_prod( 2*nodo+2, md+1, fin, p );
upd_max( nodo );
if( stprod[2*nodo+1] == -1 || stprod[2*nodo+2] == -1 )
stprod[nodo] = -1;
else if( ((ld)stprod[2*nodo+1]) > (((ld)LLONG_MAX) / ((ld)stprod[2*nodo+2])) ) //habrá overflow
stprod[nodo] = -1;
else
stprod[nodo] = stprod[2*nodo+1] * stprod[2*nodo+2];
stmodded[nodo] = (stmodded[2*nodo+1] * stmodded[2*nodo+2])%mod;
return;
}
ll updateY( ll pos, ll val )
{
y[pos] = val;
upd_y( 0, 0, n-1, pos );
return (getprod2( 0, 0, n-1, 0, stmax[0])*y[stmax[0]])%mod;
}
ll updateX( ll pos, ll val )
{
x[pos] = val;
upd_prod( 0, 0, n-1, pos );
return (getprod2( 0, 0, n-1, 0, stmax[0])*y[stmax[0]])%mod;
}
ll init( ll n_, ll x_[], ll y_[] )
{
n = n_;
for( ll i=0; i<n; i++ ){
x[i] = x_[i];
y[i] = y_[i];
}
build1( 0, 0, n-1 );
build2( 0, 0, n-1 );
return (getprod2( 0, 0, n-1, 0, stmax[0])*y[stmax[0]])%mod;
}