oj.uz

Submission #99634

# Submission time Handle Problem Language Result Execution time Memory
99634 2019-03-05T22:59:48 Z DiegoGarcia Horses (IOI15_horses) C++14
17 / 100
 367 ms 36984 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 = 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-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 = -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 ){
        assert( ini == p );
        return;
    }
    ll md = (ini+fin)/2;
    upd_y( 2*nodo+1, ini, md, p );
    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 )
    {
        assert( ini == p );
        stprod[nodo] = x[ini];
        stmodded[nodo] = x[ini]%mod;
        return;
    }
    ll md = (ini+fin)/2;
    upd_prod( 2*nodo+1, ini, md, p );
    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 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);
}

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 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);
}

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 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 3 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

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 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 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 3 ms 512 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 7 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 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Incorrect 3 ms 512 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 367 ms 36984 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 3 ms 356 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 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 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 356 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 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 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 2 ms 356 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 -