Submission #519108

#	Time	Username	Problem	Language	Result	Execution time	Memory
519108		tabr	Horses (IOI15_horses)	C++17	17 / 100	387 ms	62924 KiB

horses

#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() {
    long long prod = 1;
    vector<int> c;
    auto iter = st.rbegin();
    while (prod < (int) 1e9 && iter != st.rend()) {
        c.emplace_back(*iter);
        prod *= x[*iter];
        iter++;
    }
    long long t = 1;
    for (int i : c) {
        t = max(t, prod * seg.get(i, n).mx);
        prod /= x[i];
    }
    mint ans = t;
    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;
      |      ^

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