Submission #66222

#	Time	Username	Problem	Language	Result	Execution time	Memory
66222		daniel_02	Horses (IOI15_horses)	C++17	100 / 100	1046 ms	411620 KiB

horses

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

#define ll long long
#define fr first
#define sc second
#define double long double

using namespace std;

const int MOD = 1e9 + 7;
const int sz = 5e6 + 7;

ll n, x[sz], y[sz];
pair<double, ll> t[sz * 2], ad[sz * 2], an[sz];

pair<double, ll> maxp(pair<double, ll> a, pair<double, ll> b)
{
    if (a.fr > b.fr)
    {
        return a;
    }
    else
    {
        return b;
    }
}
ll bin_pow(ll a, ll k)
{
    if (k == 1)return a;

    if (k & 1)
        return ((a * 1LL * bin_pow(a, k - 1)) % MOD);
    else
    {
        ll b = bin_pow(a, k / 2);

        return ((b * b) % MOD);
    }
}
void build(int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v].fr = an[tl].fr;
        t[v].sc = an[tl].sc;
    }
    else
    {
        int mid = (tl + tr) >> 1;

        build(v + v, tl, mid);
        build(v + v + 1, mid + 1, tr);

        t[v] = maxp(t[v + v], t[v + v + 1]);
    }
}
void push(int v, int tl, int tr)
{
    if (ad[v].sc == -1)return;

    t[v].fr += ad[v].fr;
    t[v].sc = (ad[v].sc * t[v].sc) % MOD;

    ad[v + v].fr += ad[v].fr;
    ad[v + v + 1].fr += ad[v].fr;

    if (ad[v + v].sc == -1)ad[v + v].sc = 1;
    if (ad[v + v + 1].sc == -1)ad[v + v + 1].sc = 1;

    ad[v + v].sc = (ad[v].sc * ad[v + v].sc) % MOD;
    ad[v + v + 1].sc = (ad[v].sc * ad[v + v + 1].sc) % MOD;

    if (t[v].sc < -1)
        t[v].sc *= -1;

    ad[v].fr = 0;
    ad[v].sc = -1;
}
void updy(int v, int tl, int tr, int pos, double val, ll val1)
{
    push(v, tl, tr);
    push(v + v, tl, tr);
    push(v + v + 1, tl, tr);

    if (t[v].sc < -1)
        t[v].sc *= -1;

    if (tl == tr)
    {
        t[v].fr += val;
        t[v].sc = (t[v].sc * val1) % MOD;
    }
    else
    {
        int mid = (tl + tr) >> 1;

        if (mid >= pos)
            updy(v + v, tl, mid, pos, val, val1);
        else
            updy(v + v + 1, mid + 1, tr, pos, val, val1);

        push(v, tl, tr);
        push(v + v, tl, tr);
        push(v + v + 1, tl, tr);

        t[v] = maxp(t[v + v], t[v + v + 1]);
    }
}
void updx(int v, int tl, int tr, int l, int r, double val, ll val1)
{
    push(v, tl, tr);
    push(v + v, tl, tr);
    push(v + v + 1, tl, tr);

    if (t[v].sc < -1)
        t[v].sc *= -1;

    if (tl > r || l > tr)return;

    if (l <= tl && tr <= r)
    {
        ad[v].fr += val;
        if (ad[v].sc == -1)ad[v].sc = 1;

        ad[v].sc = (val1 * 1LL * ad[v].sc) % MOD;

        push(v, tl, tr);
        push(v + v, tl, tr);
        push(v + v + 1, tl, tr);
    }
    else
    {
        int mid = (tl + tr) >> 1;

        updx(v + v, tl, mid, l, r, val, val1);
        updx(v + v + 1, mid + 1, tr, l, r, val, val1);

        push(v, tl, tr);
        push(v + v, tl, tr);
        push(v + v + 1, tl, tr);

        t[v] = maxp(t[v + v], t[v + v + 1]);
    }
}
int init(int N, int X[], int Y[]) {

    double h = 0;
    ll cur = 1;
    double ans = 0;
    ll ans1 = 1;
    n = N;

    for (int i = 0; i < sz * 2 - 1; i++)
    {
        ad[i].sc = -1;
    }

    for (int i = 0; i < N; i++)
    {
        x[i + 1] = X[i];
        y[i + 1] = Y[i];
    }

    for (int i = 0; i < N; i++)
    {
        h += log10(X[i]);
        cur = (cur * 1LL * X[i]) % MOD;
        an[i + 1] = {h + log10(Y[i]), (cur * 1LL * Y[i]) % MOD};

        if (ans * 1.0 < h + log10(Y[i]))
        {
            ans = log10(Y[i]) + h;
            ans1 = (Y[i] * 1LL * cur) % MOD;
        }
    }

    build(1, 1, n);

    return (ans1 % MOD);
}

int updateX(int pos, int val) {
    pos++;
    double a = (log10(val) - log10(x[pos]));
    ll b = (val * 1LL * bin_pow(x[pos], MOD - 2)) % MOD;
    updx(1, 1, n, pos, n, a, b);
    x[pos] = val;
    return (t[1].sc % MOD);
}

int updateY(int pos, int val) {
    pos++;
    double a = (log10(val) - log10(y[pos]));

    ll b = (val * 1LL * bin_pow(y[pos], MOD - 2)) % MOD;

    updy(1, 1, n, pos, a, b);

    y[pos] = val;

    return (t[1].sc % MOD);
}

Compilation message (stderr)

horses.cpp: In function 'void push(int, int, int)':
horses.cpp:58:22: warning: unused parameter 'tl' [-Wunused-parameter]
 void push(int v, int tl, int tr)
                      ^~
horses.cpp:58:30: warning: unused parameter 'tr' [-Wunused-parameter]
 void push(int v, int tl, int tr)
                              ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:178:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     build(1, 1, n);
                  ^
horses.cpp:180:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (ans1 % MOD);
            ~~~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:187:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     updx(1, 1, n, pos, n, a, b);
                               ^
horses.cpp:187:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
horses.cpp:189:21: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (t[1].sc % MOD);
            ~~~~~~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:198:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     updy(1, 1, n, pos, a, b);
                            ^
horses.cpp:202:21: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (t[1].sc % MOD);
            ~~~~~~~~~^~~~~~

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