Submission #984339

#	Time	Username	Problem	Language	Result	Execution time	Memory
984339		LucaIlie	Horses (IOI15_horses)	C++17	100 / 100	1349 ms	61928 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e5;
const int MOD = 1e9 + 7;

struct AIB {
    int aib[MAX_N + 1];

    void init() {
        for ( int i = 0; i <= MAX_N; i++ )
            aib[i] = 1;
    }

    void update( int i, int x ) {
        while ( i <= MAX_N ) {
            aib[i] = (long long)aib[i] * x % MOD;
            i += (i & -i);
        }
    }

    int query( int i ) {
        int p = 1;
        while ( i > 0 ) {
            p = (long long)p * aib[i] % MOD;
            i -= (i & -i);
        }
        return p;
    }
} horses;

struct info {
    long double maxx, pos;

    info operator + ( const info &x ) const {
        if ( x.maxx > maxx )
            return x;
        return *this;
    }
};

struct AINT {
    int lst, rst;
    info aint[4 * MAX_N];
    long double lazy[4 * MAX_N];

    void init( int l, int r ) {
        lst = l;
        rst = r;
    }

    void propag( int v, int l, int r ) {
        if ( aint[v].pos == 0 )
            aint[v].pos = l;

        aint[v].maxx += lazy[v];
        if ( l != r ) {
            lazy[v * 2 + 1] += lazy[v];
            lazy[v * 2 + 2] += lazy[v];
        }
        lazy[v] = 0;
    }

    void update( int v, int l, int r, int lu, int ru, long double x ) {
        propag( v, l, r );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            lazy[v] += x;
            propag( v, l, r );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, x );
        update( v * 2 + 2, mid + 1, r, lu, ru, x );
        aint[v] = aint[v * 2 + 1] + aint[v * 2 + 2];
    }
    void update( int l, int r, long double x ) {
        update( 0, lst, rst, l, r, x );
    }

    info query( int v, int l, int r, int lq, int rq ) {
        propag( v, l, r );

        if ( l > rq || r < lq )
            return { 0, 0 };

        if ( lq <= l && r <= rq )
            return aint[v];

        int mid = (l + r) / 2;
        info a = query( v * 2 + 1, l, mid, lq, rq );
        info b = query( v * 2 + 2, mid + 1, r, lq, rq );
        return a + b;
    }
    info query( int l, int r ) {
        return query( 0, lst, rst, l, r );
    }
} cost;

int lgPut( int a, int n ) {
    if ( n == 0 )
        return 1;

    int p = lgPut( a, n / 2 );
    p = (long long)p * p % MOD;
    if ( n % 2 == 1 )
        p = (long long)p * a % MOD;

    return p;
}

int inv( int x ) {
    return lgPut( x, MOD - 2 );
}

int n;
int x[MAX_N + 1], y[MAX_N + 1];


void calc() {
    horses.init();
    cost.init( 1, n );
    for ( int i = 1; i <= n; i++ ) {
        horses.update( i, x[i] );
        cost.update( i, n, log( x[i] ) );
        cost.update( i, i, log( y[i] ) );
    }
}

int answer() {
    int i = cost.query( 1, n ).pos;
    return (long long)horses.query( i ) * y[i] % MOD;
}

int init( int N, int X[], int Y[] ) {
    n = N;

    for ( int i = n - 1; i >= 0; i-- )
        x[i + 1] = X[i], y[i + 1] = Y[i];


    calc();
    printf( "\n\n" );
    return answer();
}

int updateX( int pos, int val ) {
    int i = pos + 1;

    cost.update( i, n, -log( x[i] ) );
    horses.update( i, inv( x[i] ) );

    x[i] = val;

    cost.update( i, n, log( x[i] ) );
    horses.update( i, x[i] );

    return answer();
}

int updateY( int pos, int val ) {
    int i = pos + 1;

    cost.update( i, i, -log( y[i] ) );
    y[i] = val;
    cost.update( i, i, log( y[i] ) );


    return answer();
}

Compilation message (stderr)

horses.cpp: In member function 'void AIB::update(int, int)':
horses.cpp:19:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |             aib[i] = (long long)aib[i] * x % MOD;
      |                      ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int AIB::query(int)':
horses.cpp:27:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   27 |             p = (long long)p * aib[i] % MOD;
      |                 ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int lgPut(int, int)':
horses.cpp:111:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |     p = (long long)p * p % MOD;
      |         ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:113:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  113 |         p = (long long)p * a % MOD;
      |             ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int answer()':
horses.cpp:137:32: warning: conversion from 'long double' to 'int' may change value [-Wfloat-conversion]
  137 |     int i = cost.query( 1, n ).pos;
      |             ~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:138:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  138 |     return (long long)horses.query( i ) * y[i] % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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