Submission #312653

#	Time	Username	Problem	Language	Result	Execution time	Memory
312653		diegogrc	Horses (IOI15_horses)	C++17	100 / 100	240 ms	58564 KiB

horses

#include "horses.h"

#include<bits/stdc++.h>
#define MAX 500005
#define MOD 1000000007
#define mid (l+r)/2
#define optimiza_io cin.tie(0); ios_base::sync_with_stdio(0);
using namespace std;
typedef long long i64;

struct node
{
    double sum;
    i64 mult;
    double bestsum;
    i64 bestmult;
};

node tree[8*MAX];
i64 xx[MAX];
i64 yy[MAX];
int gN;

void unite( int x , int l , int r )
{
    tree[x].sum =  tree[l].sum + tree[r].sum;
    tree[x].mult = ( tree[l].mult * tree[r].mult ) % MOD;
    
    if( tree[l].bestsum > tree[l].sum + tree[r].bestsum )
    {
        tree[x].bestsum = tree[l].bestsum;
        tree[x].bestmult = tree[l].bestmult;
    }
    else
    {
        tree[x].bestsum = tree[l].sum + tree[r].bestsum;
        tree[x].bestmult = ( tree[l].mult * tree[r].bestmult ) % MOD;
    }
}

void initTree( int x , int l , int r )
{
    if( l == r )
    {
        tree[x].sum = log10( xx[l] );
        tree[x].mult = xx[l] % MOD;
        
        tree[x].bestsum = tree[x].sum + log10( yy[l] );
        tree[x].bestmult = ( tree[x].mult * yy[l] ) % MOD;
        return;
    }
    initTree( 2*x+1 , l , mid );
    initTree( 2*x+2 , mid+1 , r );
    unite( x , 2*x+1 , 2*x+2 );
}



int init(int N, int X[], int Y[]) {
    
    gN = N;
    for( i64 i = 0; i < N; i ++ )
        xx[i] = X[i];
    for( i64 i = 0; i < N; i ++ )
        yy[i] = Y[i];
    
    initTree( 0 , 0 , N - 1 );
    
    return ( int ) tree[0].bestmult;
}

void upd( int x , int l , int r , int q , int v , bool t )
{
    if( l > q or r < q )
        return;
    if( l == r )
    {
        if( ! t )
            xx[l] = v;
        else
            yy[l] = v;
        tree[x].sum = log10( xx[l] );
        tree[x].mult = xx[l] % MOD;
        
        tree[x].bestsum = tree[x].sum + log10( yy[l] );
        tree[x].bestmult = ( tree[x].mult * yy[l] ) % MOD;
        return;
    }
    upd( 2*x+1 , l , mid , q , v , t );
    upd( 2*x+2 , mid+1 , r , q , v , t );
    unite( x , 2*x+1 , 2*x+2 );
}

int updateX(int pos, int val) {	
    upd( 0 , 0 , gN - 1 , pos , val , 0 );
    return ( int ) tree[0].bestmult;
}

int updateY(int pos, int val) {
    upd( 0 , 0 , gN - 1 , pos , val , 1 );
    return ( int ) tree[0].bestmult;
}

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