Submission #65888

#	Time	Username	Problem	Language	Result	Execution time	Memory
65888		daniel_02	Horses (IOI15_horses)	C++17	Compilation error	0 ms	0 KiB

horses

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

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

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(long long int, long long int)':
horses.cpp:28:24: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 ll bin_pow(int a, int n)
                        ^
horses.cpp:14:5: note: shadowed declaration is here
 int n, x[sz], y[sz];
     ^
horses.cpp: In function 'void push(long long int, long long int, long long 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)
                              ^~
/tmp/cc3zI4RG.o: In function `main':
grader.c:(.text.startup+0x2db): undefined reference to `init(int, int*, int*)'
grader.c:(.text.startup+0x71a): undefined reference to `updateX(int, int)'
grader.c:(.text.startup+0x8a6): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status