Submission #99632

#	Time	Username	Problem	Language	Result	Execution time	Memory
99632		DiegoGarcia	Horses (IOI15_horses)	C++14	17 / 100	380 ms	36940 KiB

horses

#include "horses.h"
#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 = 500050, mod = 1000000007ll;
ll n;
ll x[maxn],y[maxn];
ll stprod[8*maxn]; //-1ll es overflow, sino, es normal
ll stmax[8*maxn];
ll stmodded[8*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] == -1ll || stprod[2*nodo+2] == -1ll )
        stprod[nodo] = -1ll;
    else if( ((ld)stprod[2*nodo+1]) >= (((ld)LLONG_MAX) / ((ld)stprod[2*nodo+2])) ) //habrá overflow
        stprod[nodo] = -1ll;
    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 ) // -1ll
{
    if( ini > eq || fin < sq ){
        return 1ll;
    }
    if( ini >= sq && fin <= eq )
    {
        stmodded[nodo] = x[ini];
        if( stprod[nodo] == -1ll )
            return -1ll;
        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 == -1ll || der == -1ll ) return -1ll;
    if( ((ld)izq)  >= (((ld)LLONG_MAX) / ((ld)der)) ) return -1ll;
    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-1ll, stmax[2*nodo+1] + 1, stmax[2*nodo+2] );
    if( ((ld)right_prod) >= (((ld)LLONG_MAX) / ((ld)y[stmax[2*nodo+2]]) ) )
        right_prod = -1ll;
    else
        right_prod *= y[stmax[2*nodo+2]];
    if(right_prod == -1ll || 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] == -1ll || stprod[2*nodo+2] == -1ll )
        stprod[nodo] = -1ll;
    else if( ((ld)stprod[2*nodo+1]) >= (((ld)LLONG_MAX) / ((ld)stprod[2*nodo+2])) ) //habrá overflow
        stprod[nodo] = -1ll;
    else
        stprod[nodo] = stprod[2*nodo+1] * stprod[2*nodo+2];
    stmodded[nodo] = (stmodded[2*nodo+1] * stmodded[2*nodo+2])%mod;
    return;
}

int updateY( int pos, int val )
{
    y[pos] = ((ll)val);
    upd_y( 0, 0, n-1ll, pos );
    return (int)((getprod2( 0, 0, n-1ll, 0, stmax[0])*y[stmax[0]])%mod);
}

int updateX( int pos, int val )
{
    x[pos] = ((ll)val);
    upd_prod( 0, 0, n-1ll, pos );
    return (int)((getprod2( 0, 0, n-1ll, 0, stmax[0])*y[stmax[0]])%mod);
}
int init( int N, int X[], int Y[] )
{
    n = (ll)N;
    for( ll i=0; i<N; i++ ){
        x[i] = (ll)X[i];
        y[i] = (ll)Y[i];
    }
    build1( 0, 0, n-1ll );
    build2( 0, 0, n-1ll );
    return (int)((getprod2( 0, 0, n-1ll, 0, stmax[0])*y[stmax[0]])%mod);

}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23