Submission #484793

#	Time	Username	Problem	Language	Result	Execution time	Memory
484793		jalsol	Horses (IOI15_horses)	C++17	100 / 100	392 ms	156000 KiB

horses

#include "horses.h"
#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#endif

using namespace std;

static const bool __initialization = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << setprecision(12) << fixed;
    return true;
}();

using ll = long long;
using ld = long double;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)

template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }

constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxn = 5e5 + 5;

// rewriting mint
struct mint {
    int v;
    static constexpr int mod = 1e9 + 7;

    mint() : v(0) {}
    mint(ll _v) : v(_v % mod) { v += mod * (v < 0); }

    friend mint power(mint a, ll b) {
        mint ret = 1;

        while (b) {
            if (b & 1) ret *= a;
            b >>= 1;
            a *= a;
        }

        return ret;
    }

    // TODO: add more operator
    mint& operator*=(const mint& o) {
        return *this = mint(1LL * v * o.v);
    }

    mint& operator/=(const mint& o) {
        return *this *= power(o, mod - 2);
    }

    friend mint operator*(const mint& a, const mint& b) {
        return mint(a) *= b;
    }

    friend mint operator/(const mint& a, const mint& b) {
        return mint(a) /= b;
    }

    friend bool operator==(const mint& a, const mint& b) {
        return a.v == b.v;
    }
};

void __print_single(const mint& a) {
    cerr << a.v;
}

int n;
int X[maxn];
int Y[maxn];
ld plog[maxn];
mint pprod[maxn];

namespace segtree {
struct Node {
    ld log;
    mint prod;

    Node() : log(0.0), prod(1) {}
    Node(ld x, const mint& y) : log(x), prod(y) {}

    bool operator<(const Node& o) const {
        return log < o.log;
    }

    Node& operator+=(const Node& o) {
        log += o.log;
        prod *= o.prod;
        return *this;
    }
};

void __print_single(const Node& a) {
    cerr << "{ " << a.log << ", " << a.prod.v << " }";
}

#define m ((l + r) / 2)
#define lc (2 * i + 1)
#define rc (2 * i + 2)

Node tree[maxn << 2];
Node lazy[maxn << 2];

void build(int i, int l, int r) {
    if (l == r) {
        tree[i] = {plog[l] + log(Y[l]), pprod[l] * Y[l]};
        return;
    }

    build(lc, l, m);
    build(rc, m + 1, r);
    tree[i] = max(tree[lc], tree[rc]);
}

void push(int i, int l, int r) {
    if (lazy[i].prod == 1) return;

    tree[i] += lazy[i];

    if (l < r) {
        lazy[lc] += lazy[i];
        lazy[rc] += lazy[i];
    }

    lazy[i] = Node();
}

void update(int i, int l, int r, int u, int v, const mint& mul, ld lg) {
    push(i, l, r);
    if (v < l || r < u) return;

    if (u <= l && r <= v) {
        lazy[i] = {lg, mul};
        push(i, l, r);
        return;
    }

    update(lc, l, m, u, v, mul, lg);
    update(rc, m + 1, r, u, v, mul, lg);
    tree[i] = max(tree[lc], tree[rc]);
}

#undef m
#undef lc
#undef rc
} // namespace segtree
using namespace segtree;

int init(int _N, int _X[], int _Y[]) {
    n = _N;
    mempcpy(X + 1, _X, n * sizeof(int));
    mempcpy(Y + 1, _Y, n * sizeof(int));

    plog[1] = log(X[1]);
    pprod[1] = X[1];

    For (i, 2, n) {
        plog[i] = plog[i - 1] + log(X[i]);
        pprod[i] = pprod[i - 1] * X[i];
    }

    build(0, 1, n);

    return tree[0].prod.v;
}

int updateX(int pos, int val) {
    ++pos;

    mint mul = mint(val) / mint(X[pos]);
    ld lg = -log(X[pos]) + log(val);
    X[pos] = val;

    update(0, 1, n, pos, n, mul, lg);

    return tree[0].prod.v;
}

int updateY(int pos, int val) {
    ++pos;

    mint mul = mint(val) / mint(Y[pos]);
    ld lg = -log(Y[pos]) + log(val);
    Y[pos] = val;

    update(0, 1, n, pos, pos, mul, lg);

    return tree[0].prod.v;
}

// selling everything at one single day I suppose?
// if there's an answer of selling at both days,
// then keeping instead of selling at the first day,
// keeping the number of horses grow then sell at the second day
// will profit more because of the property of exponential functions
// ig?
// but the values will get very, very large, very quickly...
// if it passes the first subtask, then the logic could be correct

// holy shit why did I forget logarithm...
// no wonder people solved this with ease

Compilation message (stderr)

horses.cpp: In constructor 'mint::mint(ll)':
horses.cpp:48:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   48 |     mint(ll _v) : v(_v % mod) { v += mod * (v < 0); }
      |                     ~~~^~~~~

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