Submission #529220

#	Time	Username	Problem	Language	Result	Execution time	Memory
529220		Cyanmond	Horses (IOI15_horses)	C++17	54 / 100	1554 ms	31212 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;
    }
}

namespace mycode {
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) {
        i += size;
        data[i] = v;
        while (i != 1) {
            i >>= 1;
            update(i);
        }
    }

    T fold(int l, int r) {
        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);
    }
};

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

SegmentTree<Monoid> seg;

int calc() {
    i64 v = 1;
    double best = (double)(Y[N - 1]);
    int best_pos = N - 1;
    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(seg.fold(0, best_pos + 1), Y[best_pos]);
}

int init(int n, std::vector<int> x, std::vector<int> y) {
    N = n;
    X = std::move(x);
    Y = std::move(y);
    seg = SegmentTree<Monoid>(N);
    for (int i = 0; i < N; ++i) seg.set(i, X[i]);
    return calc();
}

int updateX(int pos, int val) {
    X[pos] = val;
    seg.set(pos, val);
    return calc();
}

int updateY(int pos, int val) {
    Y[pos] = val;
    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 mycode::init(N, x, y);
}

int updateX(int pos, int val) {
    return mycode::updateX(pos, val);
}

int updateY(int pos, int val) {
    return mycode::updateY(pos, val);
}

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