Submission #64800

#	Time	Username	Problem	Language	Result	Execution time	Memory
64800		Kubalionzzale	Horses (IOI15_horses)	C++14	0 / 100	398 ms	29728 KiB

horses

#include "horses.h"
#include <algorithm>

int n;
long long int mod = 1e9 + 7;

long long int product[2000010] = { 0 };
long long int mediumProduct[2000010] = { 0 };
int curBest[2000010] = { 0 };
int x[500010], y[500010];

void constructProduct(int low, int high, int pos)
{
    if (low == high)
    {
        product[pos] = x[low] * 1LL;
        return;
    }

    int mid = low + (high - low) / 2;

    constructProduct(low, mid, pos * 2 + 1);
    constructProduct(mid + 1, high, pos * 2 + 2);

    product[pos] = (product[pos * 2 + 1] * product[pos * 2 + 2]) % mod;
}

void updateProduct(int qpoint, int low, int high, int pos)
{
    if (qpoint < low || qpoint > high)
        return;

    if (low == high)
    {
        product[pos] = x[low] * 1LL;
        return;
    }

    int mid = low + (high - low) / 2;

    updateProduct(qpoint, low, mid, pos * 2 + 1);
    updateProduct(qpoint, mid + 1, high, pos * 2 + 2);

    product[pos] = (product[pos * 2 + 1] * product[pos * 2 + 2]) % mod;
}

long long int queryProduct(int low, int high, int qlow, int qhigh, int pos)
{
    if (high < qlow || low > qhigh)
        return 1;

    if (qlow <= low && high <= qhigh)
    {
        return product[pos];
    }

    int mid = low + (high - low) / 2;

    return ((queryProduct(low, mid, qlow, qhigh, pos * 2 + 1) * queryProduct(mid + 1, high, qlow, qhigh, pos * 2 + 2)) % mod);
}

void constructMediumProduct(int low, int high, int pos)
{
    if (low == high)
    {
        mediumProduct[pos] = x[low] * 1LL;
        return;
    }

    int mid = low + (high - low) / 2;

    constructMediumProduct(low, mid, pos * 2 + 1);
    constructMediumProduct(mid + 1, high, pos * 2 + 2);

    long long int val = mediumProduct[pos * 2 + 1] * mediumProduct[pos * 2 + 2];

    if (val > 1e9)
        mediumProduct[pos] = 0;
    else
        mediumProduct[pos] = val;
}

void updateMediumProduct(int qpoint, int low, int high, int pos)
{
    if (qpoint < low || qpoint > high)
        return;

    if (low == high)
    {
        mediumProduct[pos] = x[low] * 1LL;
        return;
    }

    int mid = low + (high - low) / 2;

    constructMediumProduct(low, mid, pos * 2 + 1);
    constructMediumProduct(mid + 1, high, pos * 2 + 2);

    long long int val = mediumProduct[pos * 2 + 1] * mediumProduct[pos * 2 + 2];

    if (val > 1e9)
        mediumProduct[pos] = 0;
    else
        mediumProduct[pos] = val;
}

long long int queryMediumProduct(int low, int high, int qlow, int qhigh, int pos)
{
    if (high < qlow || low > qhigh)
        return 1;

    if (qlow <= low && high <= qhigh)
    {
        return mediumProduct[pos];
    }

    int mid = low + (high - low) / 2;

    long long int val1 = queryMediumProduct(low, mid, qlow, qhigh, pos * 2 + 1);
    long long int val2 = queryMediumProduct(mid + 1, high, qlow, qhigh, pos * 2 + 2);

    if (val1 * val2 > 1e9)
        return 0;
    else
        return val1 * val2;
}

int getBetter(int one, int two)
{
    long long int producted;

    producted = queryMediumProduct(0, n - 1, one + 1, two, 0);

    if (producted == 0)
        return two;
    else
    {
        long double oneans = y[one];
        long double twoans = producted * y[two];

        if (oneans > twoans)
            return one;
        else
            return two;
    }
}

void constructAnswer(int low, int high, int pos)
{
    if (low == high)
    {
        curBest[pos] = low;
        return;
    }

    int mid = low + (high - low) / 2;

    constructAnswer(low, mid, pos * 2 + 1);
    constructAnswer(mid + 1, high, pos * 2 + 2);

    curBest[pos] = getBetter(curBest[pos * 2 + 1], curBest[pos * 2 + 2]);
}

void updateAnswer(int qpoint, int low, int high, int pos)
{
    if (qpoint < low || qpoint > high)
        return;

    if (low == high)
    {
        curBest[pos] = low;
        return;
    }

    int mid = low + (high - low) / 2;

    updateAnswer(qpoint, low, mid, pos * 2 + 1);
    updateAnswer(qpoint, mid + 1, high, pos * 2 + 2);

    curBest[pos] = getBetter(curBest[pos * 2 + 1], curBest[pos * 2 + 2]);
}

int init(int N, int inx[], int iny[]) {
    n = N;

    for (int i = 0; i < n; ++i)
    {
        x[i] = inx[i];
        y[i] = iny[i];
    }

    constructProduct(0, n - 1, 0);
    constructMediumProduct(0, n - 1, 0),
    constructAnswer(0, n - 1, 0);

    return queryProduct(0, n - 1, 0, curBest[0], 0);
}

int updateX(int position, int val) {
    x[position] = val;

    updateProduct(position, 0, n - 1, 0);
    updateMediumProduct(position, 0, n - 1, 0);
    updateAnswer(position, 0, n - 1, 0);

	return queryProduct(0, n - 1, 0, curBest[0], 0);
}

int updateY(int position, int val) {

    updateAnswer(position, 0, n - 1, 0);

	return queryProduct(0, n - 1, 0, curBest[0], 0);
}

Compilation message (stderr)

horses.cpp: In function 'void constructMediumProduct(int, int, int)':
horses.cpp:77:15: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     if (val > 1e9)
               ^~~
horses.cpp: In function 'void updateMediumProduct(int, int, int, int)':
horses.cpp:101:15: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     if (val > 1e9)
               ^~~
horses.cpp: In function 'long long int queryMediumProduct(int, int, int, int, int)':
horses.cpp:122:14: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     if (val1 * val2 > 1e9)
         ~~~~~^~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:196:24: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return queryProduct(0, n - 1, 0, curBest[0], 0);
            ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:206:21: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return queryProduct(0, n - 1, 0, curBest[0], 0);
         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:213:21: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return queryProduct(0, n - 1, 0, curBest[0], 0);
         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:209:31: warning: unused parameter 'val' [-Wunused-parameter]
 int updateY(int position, int val) {
                               ^~~

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