Submission #529222

#	Time	Username	Problem	Language	Result	Execution time	Memory
529222		Cyanmond	Horses (IOI15_horses)	C++17	100 / 100	364 ms	64068 KiB

horses

// clang-format off
#include <bits/stdc++.h>

using i64 = int64_t;

template <typename T> bool setmax(T &v, const T a) {
    if (v < a) {
        v = a;
        return true;
    } else {
        return false;
    }
}

int N;
std::vector<int> X, Y;

constexpr i64 mod = 1000000007;
constexpr int max_v = 1000000000;

i64 mul(i64 v, i64 d) {
    return v * d % mod;
}

template <class M>
class SegmentTree {
    using T = typename M::Type;
    int n, size;
    std::vector<T> data;

    void update(const int i) {
        assert(0 <= i and i < size);
        data[i] = M::op(data[2 * i], data[2 * i + 1]);
    }

  public:
    SegmentTree() = default;
    SegmentTree(int n_) : n(n_) {
        size = 1;
        while (size < n) size <<= 1;
        data.assign(2 * size, M::id());
    }

    void set(int i, const T v) {
        assert(0 <= i and i < n);
        i += size;
        data[i] = v;
        while (i != 1) {
            i >>= 1;
            update(i);
        }
    }

    T fold(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        T vl = M::id(), vr = M::id();
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) vl = M::op(vl, data[l++]);
            if (r & 1) vr = M::op(data[--r], vr);
        }
        return M::op(vl, vr);
    }

    template <class F> int min_left(int r, const F& f) {
        assert(0 <= r and r <= n);
        assert(f(M::id()));
        if (r == 0) return 0;
        r += size;
        T p = M::id();
        do {
            --r;
            while (r > 1 and (r & 1)) r >>= 1;
            if (not f(M::op(data[r], p))) {
                while (r < size) {
                    r = 2 * r + 1;
                    if (f(M::op(data[r], p))) p = M::op(data[r--], p);
                }
                return r + 1 - size;
            }
            p = M::op(data[r], p);
        } while ((r & -r) != r);
        return 0;
    }
};

struct Monoid_Mul {
    using Type = i64;
    static Type op(Type a, Type b) { return mul(a, b); }
    static Type id() { return 1; }  
};

struct Monoid_Max {
    using Type = std::pair<i64, int>;
    static Type op(Type a, Type b) { return std::max(a, b); }
    static Type id() { return {0, 0}; }
};

SegmentTree<Monoid_Mul> mulseg;
SegmentTree<Monoid_Max> xseg, yseg;

int calc() {
    i64 v = 1;
    double best = (double)Y[N - 1];
    int best_pos = N - 1, r = N;
    while (v <= max_v and r != 0) {
        int nxt = xseg.min_left(r, [](const std::pair<i64, int> p) { return p.first <= 1; });
        if (nxt == 0) {
            if (setmax(best, (double)yseg.fold(nxt, r).first / (double)v)) {
                best_pos = yseg.fold(nxt, r).second;
            }
            break;
        } else {
            --nxt;
            if (setmax(best, (double)yseg.fold(nxt, r).first / (double)v)) {
                best_pos = yseg.fold(nxt, r).second;
            }
            v *= X[nxt];
            r = nxt;
        }
    }
    /*
    for (int i = N - 2; i >= 0; --i) {
        v *= X[i + 1];
        if (setmax(best, (double)Y[i] / (double)v)) {
            best_pos = i;
        }
        if (v > max_v) break;
    }
    */
    return (int)mul(mulseg.fold(0, best_pos + 1), Y[best_pos]);
}

int minit(int n, std::vector<int> x, std::vector<int> y) {
    N = n;
    X = std::move(x);
    Y = std::move(y);
    mulseg = SegmentTree<Monoid_Mul>(N);
    xseg = yseg = SegmentTree<Monoid_Max>(N);
    for (int i = 0; i < N; ++i) {
        mulseg.set(i, X[i]);
        xseg.set(i, {X[i], i});
        yseg.set(i, {Y[i], i});
    }
    return calc();
}

int mupdateX(int pos, int val) {
    X[pos] = val;
    mulseg.set(pos, val);
    xseg.set(pos, {X[pos], pos});
    return calc();
}

int mupdateY(int pos, int val) {
    Y[pos] = val;
    yseg.set(pos, {Y[pos], pos});
    return calc();
}

int init(int N, int X[], int Y[]) {
    std::vector<int> x(N), y(N);
    for (int i = 0; i < N; ++i) {
        x[i] = X[i];
        y[i] = Y[i];
    }
    return minit(N, x, y);
}

int updateX(int pos, int val) {
    return mupdateX(pos, val);
}

int updateY(int pos, int val) {
    return mupdateY(pos, val);
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:160:30: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
  160 | int init(int N, int X[], int Y[]) {
      |                          ~~~~^~~
horses.cpp:16:21: note: shadowed declaration is here
   16 | std::vector<int> X, Y;
      |                     ^
horses.cpp:160:21: warning: declaration of 'X' shadows a global declaration [-Wshadow]
  160 | int init(int N, int X[], int Y[]) {
      |                 ~~~~^~~
horses.cpp:16:18: note: shadowed declaration is here
   16 | std::vector<int> X, Y;
      |                  ^
horses.cpp:160:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  160 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:15:5: note: shadowed declaration is here
   15 | int N;
      |     ^

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