Submission #985349

#	Time	Username	Problem	Language	Result	Execution time	Memory
985349		LucaIlie	Horses (IOI15_horses)	C++17	17 / 100	161 ms	62652 KiB

horses

#include <iostream>
#include <cmath>

using namespace std;

const int mod = 1e9 + 7;
#define nmax 500000

long long aint_rez[4 * nmax];

struct info{
    double val;
    int poz;
};

info aint[4 * nmax];
double lazy[4 * nmax];
int x[nmax], y[nmax];
double sp[nmax];
int n;


void init_aint_rez( int l, int r, int poz ) {
    if( l == r ) {
        aint_rez[poz] = x[l];
        return;
    }
    init_aint_rez( l, (l + r) / 2, 2 * poz );
    init_aint_rez( (l + r) / 2 + 1, r, 2 * poz + 1 );
    aint_rez[poz] = ( aint_rez[2 * poz] * aint_rez[2 * poz + 1] ) % mod;
}

void update_aint_rez( int l, int r, int lq, int val, int poz ) {
    if( lq < l || r < lq )
        return;
    if( l == r ) {
        aint_rez[l] = val;
        return;
    }
    update_aint_rez( l, (l + r) / 2, lq, val, 2 * poz );
    update_aint_rez( (l + r) / 2 + 1, r, lq, val, 2 * poz + 1 );
    aint_rez[poz] = ( aint_rez[2 * poz] * aint_rez[2 * poz + 1] ) % mod;
}

long long query_aint_rez( int l, int r, int lq, int rq, int poz ) {
    if( r < lq || rq < l )
        return 1;
    if( lq <= l && r <= rq )
        return aint_rez[poz];
    return ( query_aint_rez( l, (l + r) / 2, lq, rq, 2 * poz ) * query_aint_rez( (l + r) / 2 + 1, r, lq, rq, 2 * poz + 1 ) ) % mod;
}

void afiseaza( int l, int r, int poz ) {
    cout << l << " " << r << " " << poz << "      "<< aint[poz].poz << " " << aint[poz].val << " " << lazy[poz] << "\n";
    if( l == r )
        return;
    afiseaza( l, (l + r) / 2, 2 * poz );
    afiseaza( (l + r) / 2 + 1, r, 2 * poz + 1 );
}

void init_aint( int l, int r, int poz ) {
    if( l == r ) {
        aint[poz].val = sp[l] + log2( y[l] );
        aint[poz].poz = l;
        return;
    }
    init_aint( l, (l + r) / 2, poz * 2 );
    init_aint( (l + r) / 2 + 1, r, poz * 2 + 1 );
    if( aint[2 * poz].val < aint[2 * poz + 1].val ) {
        aint[poz].val = aint[2 * poz + 1].val;
        aint[poz].poz = aint[2 * poz + 1].poz;
    } else{
        aint[poz].val = aint[2 * poz].val;
        aint[poz].poz = aint[2 * poz].poz;
    }
}

void push_lazy( int l, int r, int poz ) {
    aint[poz].val += lazy[poz];
    if( l < r ) {
        lazy[2 * poz] += lazy[poz];
        lazy[2 * poz + 1] += lazy[poz];
    }
    lazy[poz] = 0;
}

void update_aint( int l, int r, int ql, int qr, double val, int poz ) {
    push_lazy( l, r, poz );
    if( r < ql || qr < l )
        return;
    if( ql <= l && r <= qr ) {
        lazy[poz] = val;
    } else {
        update_aint( l, (l + r) / 2, ql, qr, val, poz * 2 );
        update_aint( (l + r) / 2 + 1, r, ql, qr, val, poz * 2 + 1 );
        if( aint[2 * poz].val < aint[2 * poz + 1].val ) {
            aint[poz].val = aint[2 * poz + 1].val;
            aint[poz].poz = aint[2 * poz + 1].poz;
        } else{
            aint[poz].val = aint[2 * poz].val;
            aint[poz].poz = aint[2 * poz].poz;
        }
    }
    push_lazy( l, r ,poz );
}

int init( int N, int X[], int Y[] ) {
    n = N;
    int i;
    for( i = 1; i <= n; i++ )
        x[i] = X[i - 1];
    for( i = 1; i <= n; i++ )
        y[i] = Y[i - 1];
    for( i = 1; i <= n; i++ )
        sp[i] = sp[i - 1] + log2( x[i] );
    init_aint_rez( 1, n, 1 );
    init_aint( 1, n, 1 );
    //afiseaza( 1, n, 1 );
    return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
}

int updateX( int poz, int val ) {
    poz++;
    update_aint( 1, n, poz, n, log2(val ) - log2( x[poz] ), 1 );
    update_aint_rez( 1, n, poz, val, 1 );
    //afiseaza( 1, n, 1 );
    return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
}

int updateY( int poz, int val ) {
    poz++;
    //cout << "\n" << log2(val ) - log2( y[poz] ) << "\n";
    update_aint( 1, n, poz, poz, log2(val ) - log2( y[poz] ), 1 );
    //afiseaza( 1, n, 1 );
    //cout << aint[1].poz << "e ";
    y[poz] = val;
    return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:119:73: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |     return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:127:73: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |     return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:137:73: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  137 |     return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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