This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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); }
| ~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |