Submission #831057

#	Time	Username	Problem	Language	Result	Execution time	Memory
831057		skittles1412	Horses (IOI15_horses)	C++17	100 / 100	537 ms	66056 KiB

horses

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using i128 = __int128_t;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T, typename Op = plus<T>>
struct ST {
    int n;
    vector<T> v, arr;
    Op op;

    ST() {}
    ST(const vector<T>& arr, const Op& op = {})
        : n(sz(arr)), v(4 * n), arr(arr), op(op) {
        build(1, 0, n - 1);
    }

    void build(int o, int l, int r) {
        if (l == r) {
            v[o] = arr[l];
            return;
        }

        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        v[o] = op(v[lc], v[rc]);
    }

    void update(int o, int l, int r, int ind, const T& x) {
        if (l == r) {
            v[o] = x;
            return;
        }

        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ind <= mid) {
            update(lc, l, mid, ind, x);
        } else {
            update(rc, mid + 1, r, ind, x);
        }
        v[o] = op(v[lc], v[rc]);
    }

    void update(int ind, const T& x) {
        update(1, 0, n - 1, ind, x);
    }

    T query(int o, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) {
            return v[o];
        }

        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ql <= mid) {
            if (mid < qr) {
                return op(query(lc, l, mid, ql, qr),
                          query(rc, mid + 1, r, ql, qr));
            }
            return query(lc, l, mid, ql, qr);
        }
        return query(rc, mid + 1, r, ql, qr);
    }

    T query(int l, int r) const {
        dbg(l, r);
        return query(1, 0, n - 1, l, r);
    }
};

struct mint {
    static constexpr int MOD = 1e9 + 7;

    static constexpr int norm(long x) {
        x %= MOD;
        if (x < 0) {
            x += MOD;
        }
        return int(x);
    }

    int x;

    constexpr mint() : x(0) {}
    constexpr mint(long x) : x(norm(x)) {}

    static mint from_unchecked(int x) {
        mint m;
        m.x = x;
        return m;
    }

    friend ostream& operator<<(ostream& out, const mint& m) {
        return out << m.x;
    }

    constexpr mint operator-() const {
        if (!x) {
            return {};
        }
        return mint::from_unchecked(MOD - x);
    }

    constexpr mint& operator+=(const mint& m) {
        x += m.x;
        if (x >= MOD) {
            x -= MOD;
        }
        return *this;
    }
    constexpr mint& operator-=(const mint& m) {
        return *this += -m;
    }

    constexpr mint& operator*=(const mint& m) {
        x = int(long(x) * m.x % MOD);
        return *this;
    }

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

template <typename T>
struct MaxOp {
    T operator()(const T& a, const T& b) const {
        return max(a, b);
    }
};

struct Solver {
    int n;
    vector<int> arr_x, arr_y;
    set<int> pos_x;
    ST<mint, multiplies<mint>> st_x;
    ST<int, MaxOp<int>> st_y;

    Solver() {}
    Solver(const vector<int>& arr_x, const vector<int>& arr_y)
        : n(sz(arr_x)),
          arr_x(arr_x),
          arr_y(arr_y),
          st_x(({
              vector<mint> v(n);
              for (int i = 0; i < n; i++) {
                  v[i] = arr_x[i];
              }
              v;
          })),
          st_y(arr_y) {
        for (int i = 0; i < n; i++) {
            if (arr_x[i] > 1) {
                pos_x.insert(i);
            }
        }
    }

    int query() {
        long opt = 0;
        mint opt_m = 0;

        auto upd = [&](long co, mint cm) -> void {
            if (co > opt) {
                opt = co;
                opt_m = cm;
            }
        };

        int prv = n;
        auto go = [&](int ind) -> void {
            mint pref_x = st_x.query(0, ind);
            int max_y = st_y.query(ind, prv - 1);
            upd(max_y, pref_x * max_y);
            dbg(ind, max_y);

            prv = ind;
            opt *= arr_x[ind];
        };

        for (auto it = pos_x.rbegin(); it != pos_x.rend() && opt < long(1e9);
             ++it) {
            go(*it);
        }

        if (prv && opt < long(1e9)) {
            assert((!sz(pos_x) && prv == n) ||
                   (sz(pos_x) && prv == *pos_x.begin()));

            mint pref_x = 1;
            int max_y = st_y.query(0, prv - 1);
            upd(max_y, pref_x * max_y);
        }

        return opt_m.x;
    }

    void update_x(int ind, int x) {
        if (arr_x[ind] > 1) {
            pos_x.erase(ind);
        }

        arr_x[ind] = x;
        st_x.update(ind, x);

        if (arr_x[ind] > 1) {
            pos_x.insert(ind);
        }
    }

    void update_y(int ind, int x) {
        arr_y[ind] = x;
        st_y.update(ind, x);
    }
} solver;

int init(int n, int arr_x[], int arr_y[]) {
    solver =
        Solver(vector<int>(arr_x, arr_x + n), vector<int>(arr_y, arr_y + n));
    return solver.query();
}

int updateX(int ind, int x) {
    solver.update_x(ind, x);
    return solver.query();
}

int updateY(int ind, int x) {
    solver.update_y(ind, x);
    return solver.query();
}

Compilation message (stderr)

horses.cpp: In constructor 'ST<T, Op>::ST(const std::vector<_Tp>&, const Op&)':
horses.cpp:36:40: warning: declaration of 'op' shadows a member of 'ST<T, Op>' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |                              ~~~~~~~~~~^~~~~~~
horses.cpp:33:8: note: shadowed declaration is here
   33 |     Op op;
      |        ^~
horses.cpp:36:25: warning: declaration of 'arr' shadows a member of 'ST<T, Op>' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |        ~~~~~~~~~~~~~~~~~^~~
horses.cpp:32:18: note: shadowed declaration is here
   32 |     vector<T> v, arr;
      |                  ^~~
horses.cpp: In constructor 'constexpr mint::mint(int64_t)':
horses.cpp:108:25: warning: declaration of 'x' shadows a member of 'mint' [-Wshadow]
  108 |     constexpr mint(long x) : x(norm(x)) {}
      |                         ^
horses.cpp:105:9: note: shadowed declaration is here
  105 |     int x;
      |         ^
horses.cpp: In constructor 'constexpr mint::mint(int64_t)':
horses.cpp:108:25: warning: declaration of 'x' shadows a member of 'mint' [-Wshadow]
  108 |     constexpr mint(long x) : x(norm(x)) {}
      |                         ^
horses.cpp:105:9: note: shadowed declaration is here
  105 |     int x;
      |         ^
horses.cpp: In constructor 'constexpr mint::mint(int64_t)':
horses.cpp:108:25: warning: declaration of 'x' shadows a member of 'mint' [-Wshadow]
  108 |     constexpr mint(long x) : x(norm(x)) {}
      |                         ^
horses.cpp:105:9: note: shadowed declaration is here
  105 |     int x;
      |         ^
horses.cpp: In constructor 'Solver::Solver(const std::vector<int>&, const std::vector<int>&)':
horses.cpp:169:57: warning: declaration of 'arr_y' shadows a member of 'Solver' [-Wshadow]
  169 |     Solver(const vector<int>& arr_x, const vector<int>& arr_y)
      |                                      ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:163:24: note: shadowed declaration is here
  163 |     vector<int> arr_x, arr_y;
      |                        ^~~~~
horses.cpp:169:31: warning: declaration of 'arr_x' shadows a member of 'Solver' [-Wshadow]
  169 |     Solver(const vector<int>& arr_x, const vector<int>& arr_y)
      |            ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:163:17: note: shadowed declaration is here
  163 |     vector<int> arr_x, arr_y;
      |                 ^~~~~
horses.cpp: In constructor 'Solver::Solver(const std::vector<int>&, const std::vector<int>&)':
horses.cpp:169:57: warning: declaration of 'arr_y' shadows a member of 'Solver' [-Wshadow]
  169 |     Solver(const vector<int>& arr_x, const vector<int>& arr_y)
      |                                      ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:163:24: note: shadowed declaration is here
  163 |     vector<int> arr_x, arr_y;
      |                        ^~~~~
horses.cpp:169:31: warning: declaration of 'arr_x' shadows a member of 'Solver' [-Wshadow]
  169 |     Solver(const vector<int>& arr_x, const vector<int>& arr_y)
      |            ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:163:17: note: shadowed declaration is here
  163 |     vector<int> arr_x, arr_y;
      |                 ^~~~~
horses.cpp: In constructor 'Solver::Solver(const std::vector<int>&, const std::vector<int>&)':
horses.cpp:169:57: warning: declaration of 'arr_y' shadows a member of 'Solver' [-Wshadow]
  169 |     Solver(const vector<int>& arr_x, const vector<int>& arr_y)
      |                                      ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:163:24: note: shadowed declaration is here
  163 |     vector<int> arr_x, arr_y;
      |                        ^~~~~
horses.cpp:169:31: warning: declaration of 'arr_x' shadows a member of 'Solver' [-Wshadow]
  169 |     Solver(const vector<int>& arr_x, const vector<int>& arr_y)
      |            ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:163:17: note: shadowed declaration is here
  163 |     vector<int> arr_x, arr_y;
      |                 ^~~~~
horses.cpp: In instantiation of 'ST<T, Op>::ST(const std::vector<_Tp>&, const Op&) [with T = mint; Op = std::multiplies<mint>]':
horses.cpp:180:21:   required from here
horses.cpp:36:40: warning: declaration of 'op' shadows a member of 'ST<mint, std::multiplies<mint> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |                              ~~~~~~~~~~^~~~~~~
horses.cpp:33:8: note: shadowed declaration is here
   33 |     Op op;
      |        ^~
horses.cpp:36:25: warning: declaration of 'arr' shadows a member of 'ST<mint, std::multiplies<mint> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |        ~~~~~~~~~~~~~~~~~^~~
horses.cpp:32:18: note: shadowed declaration is here
   32 |     vector<T> v, arr;
      |                  ^~~
horses.cpp:36:40: warning: declaration of 'op' shadows a member of 'ST<mint, std::multiplies<mint> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |                              ~~~~~~~~~~^~~~~~~
horses.cpp:33:8: note: shadowed declaration is here
   33 |     Op op;
      |        ^~
horses.cpp:36:25: warning: declaration of 'arr' shadows a member of 'ST<mint, std::multiplies<mint> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |        ~~~~~~~~~~~~~~~~~^~~
horses.cpp:32:18: note: shadowed declaration is here
   32 |     vector<T> v, arr;
      |                  ^~~
horses.cpp:36:40: warning: declaration of 'op' shadows a member of 'ST<mint, std::multiplies<mint> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |                              ~~~~~~~~~~^~~~~~~
horses.cpp:33:8: note: shadowed declaration is here
   33 |     Op op;
      |        ^~
horses.cpp:36:25: warning: declaration of 'arr' shadows a member of 'ST<mint, std::multiplies<mint> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |        ~~~~~~~~~~~~~~~~~^~~
horses.cpp:32:18: note: shadowed declaration is here
   32 |     vector<T> v, arr;
      |                  ^~~
horses.cpp: In instantiation of 'ST<T, Op>::ST(const std::vector<_Tp>&, const Op&) [with T = int; Op = MaxOp<int>]':
horses.cpp:180:21:   required from here
horses.cpp:36:40: warning: declaration of 'op' shadows a member of 'ST<int, MaxOp<int> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |                              ~~~~~~~~~~^~~~~~~
horses.cpp:33:8: note: shadowed declaration is here
   33 |     Op op;
      |        ^~
horses.cpp:36:25: warning: declaration of 'arr' shadows a member of 'ST<int, MaxOp<int> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |        ~~~~~~~~~~~~~~~~~^~~
horses.cpp:32:18: note: shadowed declaration is here
   32 |     vector<T> v, arr;
      |                  ^~~
horses.cpp:36:40: warning: declaration of 'op' shadows a member of 'ST<int, MaxOp<int> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |                              ~~~~~~~~~~^~~~~~~
horses.cpp:33:8: note: shadowed declaration is here
   33 |     Op op;
      |        ^~
horses.cpp:36:25: warning: declaration of 'arr' shadows a member of 'ST<int, MaxOp<int> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |        ~~~~~~~~~~~~~~~~~^~~
horses.cpp:32:18: note: shadowed declaration is here
   32 |     vector<T> v, arr;
      |                  ^~~
horses.cpp:36:40: warning: declaration of 'op' shadows a member of 'ST<int, MaxOp<int> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |                              ~~~~~~~~~~^~~~~~~
horses.cpp:33:8: note: shadowed declaration is here
   33 |     Op op;
      |        ^~
horses.cpp:36:25: warning: declaration of 'arr' shadows a member of 'ST<int, MaxOp<int> >' [-Wshadow]
   36 |     ST(const vector<T>& arr, const Op& op = {})
      |        ~~~~~~~~~~~~~~~~~^~~
horses.cpp:32:18: note: shadowed declaration is here
   32 |     vector<T> v, arr;
      |                  ^~~

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