답안 #99630 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99630	2019-03-05T22:41:46 Z	DiegoGarcia	말 (IOI15_horses)	C++14	17 / 100	377 ms	40720 KB

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	377 ms	40720 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #99630

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 0 / 17.0

Subtask #3 0 / 20.0

Subtask #4 0 / 23.0

Subtask #5 0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
0 / 17.0

Subtask #3
0 / 20.0

Subtask #4
0 / 23.0

Subtask #5
0 / 23.0