답안 #99634 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99634	2019-03-05T22:59:48 Z	DiegoGarcia	말 (IOI15_horses)	C++14	17 / 100	367 ms	36984 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 = 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

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

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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	367 ms	36984 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	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

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

답안 #99634

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