Submission #484793

#TimeUsernameProblemLanguageResultExecution timeMemory
484793jalsolHorses (IOI15_horses)C++17
100 / 100
392 ms156000 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...