Submission #65882

#	Time	Username	Problem	Language	Result	Execution time	Memory
65882		daniel_02	Horses (IOI15_horses)	C++17	17 / 100	387 ms	88596 KiB

horses

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

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

using namespace std;

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

int n, x[sz], y[sz];
pair<double, ll> t[sz * 7], ad[sz * 7], 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(int a, int n)
{
    if (n == 1)return a;

    if (n & 1)
        return ((a * 1LL * bin_pow(a, n - 1)) % MOD);
    else
    {
        ll b = bin_pow(a, n / 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;

    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;

    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);
    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);

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

    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);
    }
    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);

        t[v] = maxp(t[v + v], t[v + v + 1]);
    }
}
void get(int v, int tl, int tr, int pos)
{
    push(v, tl, tr);
    if (tl == tr)
    {
        cout << t[v].fr << " " << t[v].sc << endl;
    }
    else
    {
        int mid = (tl + tr) >> 1;

        if (mid >= pos)
            get(v + v, tl, mid, pos);
        else
            get(v + v + 1, mid + 1, tr, pos);

        push(v, 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 * 7 - 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 * 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 * bin_pow(x[pos], MOD - 2)) % MOD;
    updx(1, 1, n, pos, n, a, b);
    x[pos] = val;
    return t[1].sc;
}

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

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

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

    y[pos] = val;

    return t[1].sc;
}

Compilation message (stderr)

horses.cpp: In function 'long long int bin_pow(int, int)':
horses.cpp:27:24: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 ll bin_pow(int a, int n)
                        ^
horses.cpp:13:5: note: shadowed declaration is here
 int n, x[sz], y[sz];
     ^
horses.cpp: In function 'void push(int, int, int)':
horses.cpp:57:22: warning: unused parameter 'tl' [-Wunused-parameter]
 void push(int v, int tl, int tr)
                      ^~
horses.cpp:57: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:174: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:6:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define sc second
            ^
horses.cpp:183:17: note: in expansion of macro 'sc'
     return t[1].sc;
                 ^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:6:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define sc second
            ^
horses.cpp:196:17: note: in expansion of macro 'sc'
     return t[1].sc;
                 ^~

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