Submission #519110

#TimeUsernameProblemLanguageResultExecution timeMemory
519110tabrHorses (IOI15_horses)C++17
100 / 100
378 ms62952 KiB
#include <bits/stdc++.h> using namespace std; #ifdef tabr #include "library/debug.cpp" #else #define debug(...) #endif template <long long mod> struct modular { long long value; modular(long long x = 0) { value = x % mod; if (value < 0) value += mod; } modular& operator+=(const modular& other) { if ((value += other.value) >= mod) value -= mod; return *this; } modular& operator-=(const modular& other) { if ((value -= other.value) < 0) value += mod; return *this; } modular& operator*=(const modular& other) { value = value * other.value % mod; return *this; } modular& operator/=(const modular& other) { long long a = 0, b = 1, c = other.value, m = mod; while (c != 0) { long long t = m / c; m -= t * c; swap(c, m); a -= t * b; swap(a, b); } a %= mod; if (a < 0) a += mod; value = value * a % mod; return *this; } friend modular operator+(const modular& lhs, const modular& rhs) { return modular(lhs) += rhs; } friend modular operator-(const modular& lhs, const modular& rhs) { return modular(lhs) -= rhs; } friend modular operator*(const modular& lhs, const modular& rhs) { return modular(lhs) *= rhs; } friend modular operator/(const modular& lhs, const modular& rhs) { return modular(lhs) /= rhs; } modular& operator++() { return *this += 1; } modular& operator--() { return *this -= 1; } modular operator++(int) { modular res(*this); *this += 1; return res; } modular operator--(int) { modular res(*this); *this -= 1; return res; } modular operator-() const { return modular(-value); } bool operator==(const modular& rhs) const { return value == rhs.value; } bool operator!=(const modular& rhs) const { return value != rhs.value; } bool operator<(const modular& rhs) const { return value < rhs.value; } }; template <long long mod> string to_string(const modular<mod>& x) { return to_string(x.value); } template <long long mod> ostream& operator<<(ostream& stream, const modular<mod>& x) { return stream << x.value; } template <long long mod> istream& operator>>(istream& stream, modular<mod>& x) { stream >> x.value; x.value %= mod; if (x.value < 0) x.value += mod; return stream; } constexpr long long mod = (long long) 1e9 + 7; using mint = modular<mod>; mint power(mint a, long long n) { mint res = 1; while (n > 0) { if (n & 1) { res *= a; } a *= a; n >>= 1; } return res; } vector<mint> fact(1, 1); vector<mint> finv(1, 1); mint C(int n, int k) { if (n < k || k < 0) { return mint(0); } while ((int) fact.size() < n + 1) { fact.emplace_back(fact.back() * (int) fact.size()); finv.emplace_back(mint(1) / fact.back()); } return fact[n] * finv[k] * finv[n - k]; } struct segtree { struct T { int mx; mint prod; }; int n; int size; vector<T> node; T e() { return T{-1, mint(1)}; } T op(T x, T y) { return T{max(x.mx, y.mx), x.prod * y.prod}; } segtree() : segtree(0) {} segtree(int _n) { build(vector<T>(_n, e())); } segtree(const vector<T>& v) { build(v); } void build(const vector<T>& v) { n = (int) v.size(); if (n <= 1) { size = n; } else { size = 1 << (32 - __builtin_clz(n - 1)); } node.resize(2 * size, e()); for (int i = 0; i < n; i++) { node[i + size] = v[i]; } for (int i = size - 1; i > 0; i--) { node[i] = op(node[2 * i], node[2 * i + 1]); } } void set(int p, T v) { assert(0 <= p && p < n); p += size; node[p] = v; // update // node[p] += v; // add while (p > 1) { p >>= 1; node[p] = op(node[2 * p], node[2 * p + 1]); } } T get(int l, int r) { assert(0 <= l && l <= r && r <= n); T vl = e(); T vr = e(); l += size; r += size; while (l < r) { if (l & 1) { vl = op(vl, node[l++]); } if (r & 1) { vr = op(node[--r], vr); } l >>= 1; r >>= 1; } return op(vl, vr); } T get(int p) { assert(0 <= p && p < n); return node[p + size]; } }; int n; int* x; int* y; set<int> st; segtree seg; int f() { __int128_t prod = 1; vector<int> c; auto iter = st.rbegin(); while (prod < (int) 1e9 && iter != st.rend()) { c.emplace_back(*iter); prod *= x[*iter]; iter++; } __int128_t t = 1; for (int i : c) { int s = seg.get(i, n).mx; if (t < prod * s) { t = prod * s; } prod /= x[i]; } mint ans = (long long) (t % mod); ans *= seg.get(0, c.back()).prod; return (int) ans.value; } int init(int _n, int _x[], int _y[]) { n = _n; x = _x; y = _y; st.emplace(0); for (int i = 0; i < n; i++) { if (x[i] > 1) { st.emplace(i); } } seg = segtree(n); for (int i = 0; i < n; i++) { seg.set(i, segtree::T{y[i], x[i]}); } return f(); } int updateX(int pos, int val) { x[pos] = val; if (x[pos] > 1) { st.emplace(pos); } else if (pos != 0) { st.erase(pos); } seg.set(pos, segtree::T{y[pos], x[pos]}); return f(); } int updateY(int pos, int val) { y[pos] = val; seg.set(pos, segtree::T{y[pos], x[pos]}); return f(); } #ifdef tabr int main() { ios::sync_with_stdio(false); cin.tie(0); int _n = 3; int _x[] = {2, 1, 3}; int _y[] = {3, 4, 1}; cout << init(_n, _x, _y) << '\n'; cout << updateY(1, 2) << '\n'; return 0; } #endif

Compilation message (stderr)

horses.cpp: In instantiation of 'modular<mod>::modular(long long int) [with long long int mod = 1000000007]':
horses.cpp:83:16:   required from here
horses.cpp:12:23: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   12 |     modular(long long x = 0) {
      |             ~~~~~~~~~~^~~~~
horses.cpp:186:6: note: shadowed declaration is here
  186 | int* x;
      |      ^
horses.cpp:12:23: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   12 |     modular(long long x = 0) {
      |             ~~~~~~~~~~^~~~~
horses.cpp:186:6: note: shadowed declaration is here
  186 | int* x;
      |      ^
#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...