oj.uz

Submission #99630

# Submission time Handle Problem Language Result Execution time Memory
99630 2019-03-05T22:41:46 Z DiegoGarcia Horses (IOI15_horses) C++14
17 / 100
 377 ms 40720 KB 
#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 = 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;
}

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

int updateX( int pos, int val )
{
    x[pos] = (ll)val;
    upd_prod( 0, 0, n-1, pos );
    return (int)(getprod2( 0, 0, n-1, 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-1 );
    build2( 0, 0, n-1 );
    return (int)(getprod2( 0, 0, n-1, 0, stmax[0])*y[stmax[0]])%mod;

}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 464 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 10 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Incorrect 2 ms 384 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 377 ms 40720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 16 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Incorrect 2 ms 384 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 284 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Incorrect 2 ms 384 KB Output isn't correct
22 Halted 0 ms 0 KB -